The Gateway to Computer Science Excellence
0 votes
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
in Algorithms by Junior (775 points)
retagged by | 35 views
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 .

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
104,889 users