All categories

1 year ago

Prove that f(n) = 20n3 + 10nlogn + 5 is O(n3)

Computers and Technology

1 answer:

sp2606 [1]1 year ago

7 0

Answer:

The proof is in the explanation

Explanation:

$f(n)$ is $O(n^{3})$ if $f(n) \leq cn^{3}$ for $n \geq n_{0}$ .

So, basically, we have to solve the following inequality

$f(n) \leq cn^{3}$

$20n^{3} + 10n\log{n} + 5 \leq cn^{3}$

Dividing everything by $n^{3}$ to simplify, we have

$20 + \frac{10\log{n}}{n^{2}} + \frac{5}{n^{3}} \leq cn^{3}$

I am going to use $n = n_{0} = 1$ . So

$20 + 5 \leq c$

$c \geq 25$

There is a solution for the inequality, which proves that $f(n) = 20n^{3} + 10n\log{n} + 5$ is $O(n^{3})$

You might be interested in

Where does an MPLS label go in a PDU?

Natalija [7]

Answer: Between Layers 2 and 3

Explanation:

In between Layer 2 and Layer 3 the MPLS header is present and is known as Shim header. It is also said to be in 2.5.

6 0

1 year ago

Replace the underlines with the words in parentheses that follow: the ____ solves the ____ of a ____ by expressing an ____ in a

adell [148]

The programmer solves the problems of a user by expressing an algorithm in a programming language to make a program that can run on a computer.

5 0

2 years ago

Row array gameScores contains all player scores. Construct a row array highScores than contains all player scores greater than m

Sever21 [200]

Answer:

The solution is written using Python as it has a simple syntax.

def getHighScores(gameScores, minScore):
meetsThreshold = []
for score in gameScores:
if(score > minScore):
meetsThreshold.append(score)
return meetsThreshold
gameScores = [2, 5, 7, 6, 1, 9, 1]
minScore = 5
highScores = getHighScores(gameScores, minScore)
print(highScores)

Explanation:

Line 1-8

Create a function and name it as getHighScores which accepts two values, gameScores and minScore. (Line 1)
Create an empty list/array and assign it to variable meetsThreshold. (Line 2)
Create a for loop to iterate through each of the score in the gameScores (Line 4)
Set a condition if the current score is bigger than the minScore, add the score into the meetsThreshold list (Line 5-6)
Return meetsThreshold list as the output

Line 11-12

create a random list of gameScores (Line 11)
Set the minimum score to 5 (Line 12)

Line 13-14

Call the function getHighScores() and pass the gameScores and minScore as the arguments. The codes within the function getHighScores() will run and return the meetsThreshold list and assign it to highScores. (Line 13)
Display highScores using built-in function print().

8 0

1 year ago

HackerCards is a trendy new card game. Each type of HackerCard has a distinct ID number greater than or equal to 1, and the cost

joja [24]

Answer:

I don't know if this is right output is {1,3}

Explanation:

5 0

1 year ago

A regional bank implemented an automated solution to streamline their operations for receiving and processing checks/cheques. Th

Sphinxa [80]

Answer: Machine learning

Explanation:

The technology that could be combined with the current solution to do this is the machine learning.

Machine learning refers to the use and development of the computer systems which can learn and adapt without them following explicit instructions. This is done through the use of statistical models and algorithms in order to analyse inferences from the patterns in data.

Since the bank wants to streamline their operations for the receiving and processing checks while also enhancing the solution to recognize signs of potential check fraud, then the machine learning can be used.

3 0

1 year ago