Question

In this problem you will prove there is a function that is in O(n, and Ω(n) but is not in Θ(nd) for any 1 sds3. State a function f(n) that is in O(3) and 2(n) but is not in (n) for anylsds3 Prove that f(n)gn forany1sds3.

Answer 1

Solution:

Our function is f(n)= n^2 log n

Let's have a look at Big-O and Big-$\Omega$ first.

Proof:

f(n)= O(n^3)

because

n^2 log n<= c * n^3

The above inequality is true

f(n)= $\Omega$(n)

because

n^2 log n>= c * n

The above inequality is true

but

f(n)$\neq \Theta (n^d)$

because

for any value of d and the constant c, log n cannot be compared and equated.

since its in the form of n and not a constant.

Hence the solution.

Please give it a thumbs up if this helped you, also provide your valuable feedback.