5 votes 5 votes Where c is constant. Algorithms algorithms recurrence-relation + – piyushkr asked Dec 23, 2015 • retagged Jul 9, 2022 by Lakshman Bhaiya piyushkr 5.1k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 10 votes 10 votes I am getting $\Theta$ (2^n) . Riya Roy(Arayana) answered Dec 23, 2015 • selected Dec 23, 2015 by Arjun Riya Roy(Arayana) comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Arjun commented Dec 26, 2015 reply Follow Share Unless we approximate we always get $\Theta$. Theta says = while O says <=. So, Theta is more appropriate if it can be used. 2 votes 2 votes radha gogia commented Dec 26, 2015 reply Follow Share 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 . 0 votes 0 votes Arjun commented Dec 26, 2015 reply Follow Share 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)$. 2 votes 2 votes Please log in or register to add a comment.