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

1 Answer

+8 votes
Best answer

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

answered by Boss (6.8k 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)$.

Related questions

Top Users Jan 2017
  1. Debashish Deka

    7638 Points

  2. Habibkhan

    4716 Points

  3. Vijay Thakur

    4448 Points

  4. sudsho

    4316 Points

  5. saurabh rai

    4180 Points

  6. Arjun

    3458 Points

  7. santhoshdevulapally

    3450 Points

  8. Bikram

    3240 Points

  9. GateSet

    3202 Points

  10. Sushant Gokhale

    3042 Points

Monthly Topper: Rs. 500 gift card

18,900 questions
23,865 answers
51,944 comments
20,189 users