#algorithm

61 views
Write the Big-O notation for the following functions. Mention if they are exponential,
polynomial, logarithmic or neither of those. Proof is not required, but write one or

(a) n log n + .01n$^{3/2}$  + 10n
(b) $\frac{log n!}{n}$
(c) 1.01$^{n}$ + n3
(d) .99$^{n}$ + n
(e) log(n + n – 1 + ……..+ 1)
(f) n.$^{.01}$ + log n2

retagged
0
a. Polynomial. Since $0.01n^{3/2}$ is the dominating term.

b. Logarithmic. Since n! can be replaced with $n^n$

c. Exponential. $1.01^n$ is dominating term here.

d. Polynomial.

e. Logarithmic.

f. Polynomial
0
how come n! be n^n ??
0
I read it Cormen,  n! Has upper bound of O($n^n$).

Maybe n! = n(n-1)(n-2).... = $n^n$ + other terms
0

Yes true , log(n!) is asymptotically equal to θ(nlogn) since the lower order terms do not matter .

You explained it clearly , n! = n(n-1)(n-2)....1 where the highest order term will be n^n .

Related questions

What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$