Complexity Analysis

general
1

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:

  1. Can we say that a^{f(n)} is \theta(a^{g(n)}) or O(a^{g(n)}) a > 1
  2. 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

1 Like
2

I remember a very good question on time complexity.

Consider this question F - Three Variables Game

Consider the following idea. Let us choose randomly. If there is a point at which both options do not work, we undo the last choice, until we can use another option. Then we try the other option.

The code : Submission #15585466 - AtCoder Beginner Contest 166

If trying each option and undoing each operation is implemented in O(1), Prove that this algorithm is O(N).