T(n) = 2 T(n/2) + 2 T(2) = 1 T(1) = 0 We can solve this recurrence relation by master method/recursion tree method. if n is a power of 2 T(n) = 3n/2 - 2