GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
280 views
Where c is constant.
asked in Algorithms by (311 points)   | 280 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)$.
Members at the site
Top Users Feb 2017
  1. Arjun

    4680 Points

  2. Bikram

    4004 Points

  3. Habibkhan

    3738 Points

  4. Aboveallplayer

    2966 Points

  5. sriv_shubham

    2278 Points

  6. Smriti012

    2212 Points

  7. Arnabi

    1814 Points

  8. Debashish Deka

    1788 Points

  9. sh!va

    1444 Points

  10. mcjoshi

    1444 Points

Monthly Topper: Rs. 500 gift card

20,788 questions
25,938 answers
59,533 comments
21,926 users