Doubt in Time Complexity MCQ assignment

#1

Q2) Time complexity of finding minimum in a stack after each pop(). According to me it should be O(n) since to find minimum I should pop out all the elements in the stack and go through them… But it is given O(1) as the answer.

Q3) Time complexity to find nth fibonacci number. How is the answer O(log n)?

Q13) How do we say that this is omega (n^2) and not O(n^2)?

Thanks in advance!

#2

Hey ! for fibonacci sequence you can find it in O(logn ) using many ways.

  1. Matrix Exponentiation
  2. Using Odd-Even technique
    Suppose k=n/2;
    if(n is even)
    f(2 * k) = f(k) * f(k) + f(k - 1) * f(k - 1)
    else
    f(2 * k + 1) = f(k) * f(k + 1) + f(k - 1) * f(k)

And for stack problem i think there is something more that you are missing …