1 votes 1 votes What is the running time of following recurrence relation? T(n) = T(n/2) + T(n/4) + T(n/8) + n Ashwani Kumar 2 asked Sep 8, 2016 Ashwani Kumar 2 382 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes using recurrence tree method ans is theta(n). saurabh rai answered Sep 8, 2016 saurabh rai comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Can be written as T(n) = T(n/2) + theta(n). T(n) = n + n/2 +n/4 + n/8......... T(n) = n(1 + 1/2 +1/4......). T(n) = n*1. T(n) = theta(n) Arpit Dhuriya answered Sep 8, 2016 Arpit Dhuriya comment Share Follow See all 2 Comments See all 2 2 Comments reply Ashwani Kumar 2 commented Sep 8, 2016 reply Follow Share Why have you ignored the T(n/4) and T(n/8) 0 votes 0 votes Arpit Dhuriya commented Sep 8, 2016 reply Follow Share Because the computation time taken by them is less in comparison to T(n/2), so we can neglect them to get the got idea. 0 votes 0 votes Please log in or register to add a comment.
