The Gateway to Computer Science Excellence
0 votes
35 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
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
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 .

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
198,209 comments
104,889 users