how to solve this recursive function T(n) = T(n/2) + O(n)

29 Views Asked by At
T(n) = O(1) + O(1) + T(n/2) + T(n/2) + O(n)
= T(n/2) + O(n)
= (T(n/4) + O(n/2))+ O(n)
= ((T(n/8)+ O(n/4)) + O(n/2))+ O(n)
= T(n/2k ) + O(n)
= O(n)

Base condition: T(1) = 1. Can someone please help me where i am going wrong

1

There are 1 best solutions below

0
On

T(n/2) + T(n/2) is not simply T(n/2); it is 2 T(n/2).