Iteration Method

don't guess, grunt

T (n) = 3 T ( ë n/4 û ) + n

= 3 ( 3 T ( ë n/16 û ) +  ë n/4 û ) + n

= 3 ( 3 ( 3 T ( ë n/64 û ) +  ë n/16 û ) +  ë n/4 û ) + n

= n  + 3 ë n/4 û + 9  ë n/16 û + 27 ( T ( ë n/64 û )

How far can this go on? until n / 4ⁱ £ 1 Þ n £ 4ⁱ  Þ log₄ n £ i

T (n) = n + 3 ë n/4 û + ... + 3ⁱ  ë n/4ⁱ  û + 3 ^{log₄ n} Q(1)

T (n) £ n + 3 n / 4 + 9 n / 16 + ... + 3 ^{log₄ n} Q(1)

£

¥ n å   (3/4)i  + Q(n log4 3)    k = 0

as 3 log4 n = n log4 3

 £  n ( 1 / (1- 3/4) ) + O (n) = 4 n   +  O (n)  = O (n)
note:  log₄ 3 < 1

To make iteration method work you must determine:

1. The general term -- for example n ( 3/4 )ⁱ
2. The number of terms log₄ n

Short cut: ë n/4 û = n/4 when n = 4^k . Can solve the easy case to get an answer and then check.