Using the substitution method show that Tn On for the recur

Using the substitution method, show that T(n) = O(n) for the recurrence T(n) = T(n/2) + T(n/3) + O(n)

Solution

Answer:

This is a recurrence involving more than 1 branch. So substitution method is not suitable . We can solve it using tree method :

See cost of a level is found by f(n) and f(n) = n here .So cost at 1st level = O(n)

Cost at 2nd level = n/2 + n/3 = 5n/6 . Similarly cost at 3rd level = n/4 + n/6 + n/6 + n/9 = 25n/36 . So u can see cost is decreasing at each level and forming a decreasing GP having common ratio = 5/6

So T(n) = total cost = n + 5n/6 + 25n/36 +...

= n(1 + 5/6 + 25/36 + .....) = kn for some constant k

since it is a decreasing GP so we can consider the inside series sum as some contant so T(n) = kn

(or) T(n) = O(n)