GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
307 views
Where c is constant.
asked in Algorithms by (311 points)   | 307 views

1 Answer

+8 votes
Best answer

I am getting $\Theta$ (2^n) .

answered by Boss (7k points)  
selected by
You should use $\Theta$ though $O$ is not wrong here :)
Done.
Very nicely explained. Thanks for the answer. :)
Sir ,how to get the intution while solving a recurrence whether we should use theta or Big-O ?And why  here theta is more appropriate ?
Unless we approximate we always get $\Theta$. Theta says = while O says <=. So, Theta is more appropriate if it can be used.
But theta(n) is used when T(n) =Omega(n) as well as O(n) , so seeing the above solution how to conclude that both of them are asymptotically same .
Here, it is other way. In the proof all statements were "=". So, finally we can say it is $\Theta(2^n)$ and hence $O(2^n)$ and $\Omega(2^n)$.


Top Users Apr 2017
  1. akash.dinkar12

    3514 Points

  2. Divya Bharti

    2546 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,042 answers
63,233 comments
24,135 users