Hi everyone,
Today I was going through some complexity Analysis Problems and found some good questions, so I thought to post them here:
1.Consider two functions f(n) and g(n) such that f(n) is \theta(g(n)), then:
- Can we say that a^{f(n)} is \theta(a^{g(n)}) or O(a^{g(n)}) a > 1
- Can we say that log(f(n)) is \theta(log(g(n))) or O(log(g(n)))
Also you can assume that f(n) > 0 and g(n) > 0 for all n
2.Prove that log(n!) is \theta(n*log(n))
These questions maybe beneficial for beginners but higher rated coders are more than welcome to provide answers to these problems.
If you guys have some other tricky complexity analysis problems please post them here.
I’ll post the solution in case someone is interested in knowing them.
Thanks