#algorithm

Question

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
two sentences about how you arrived at the answer.

(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

Comments

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

---

how come n! be n^n ??

---

I read it Cormen,  n! Has upper bound of O($n^n$).

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

---

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 .