Asymptotic Notation

Question

Big 'O' estimate for Factorial Functions and Logarithm of Factorial Function i.e. n! and log n! is

a)O(n!) and O(n log n)

b)O(nn) and O(n log n)

c)O(n!) and O(log n!)

d)O(nn) and O(log n!)

Answer 1

Conceptually all options are correct 
Because Big Oh means   f(n) = O(g(n))            f(n) is less than or equal to g(n)

look first of all n! = n*(n-1)*(n-2)*..........*1 < n*n*n*........
so N^N can be upper bound to n! 
2nd is log(n!) = log(n*(n-1)*(n-2)*..........*1)   < log(n*n*n*........)

and log(nⁿ) = n*logn which can be a upper bound to log(n!)

 

Comments

@aehkn, I haven't understood this part, especially n! is no doubt less than nⁿ. But why nⁿ is being upper bound to n!? This u explain. Yeah. :)

---

take whatever value of n  n! will always be less than or equal to nⁿ

Big O means n! will always be less than or equal to n power n so its an upper bound

---

Thanks again. :)

---

Actually, Big Oh means the value greater than or equal to.

so if you have fact(n) then we know n^n is greater than that.

so we took to log on both sides and we got log(fact(n))<=log(n*log(n)).

Answer 2

b) should be correct

Since n! < n^n

So n! = O(n^n) (This bound is more strict) and log(n!) =O( n log(n))

Answer 3

Option b

Comments

@Purvi, Please work it out if u can. It'd be a big help indeed. :)