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 Arjun commented Dec 23, 2015 reply Follow Share You should use $\Theta$ though $O$ is not wrong here :) 1 votes 1 votes Riya Roy(Arayana) commented Dec 23, 2015 reply Follow Share Done. 1 votes 1 votes piyushkr commented Dec 23, 2015 reply Follow Share Very nicely explained. Thanks for the answer. :) 1 votes 1 votes radha gogia commented Dec 25, 2015 reply Follow Share 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 ? 0 votes 0 votes 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.