Recursion Trees
Consider T (n) = 2 T ( n/2 ) + n2
| level1 |
|
|
|
n2 |
|
|
= n2 |
| level2 |
|
(n/2)2 |
|
|
(n/2)2 |
|
= n2/2 |
| level3 |
(n/4)2 |
|
(n/4)2 |
(n/4)2 |
|
(n/4)2 |
= n2/4 |
How far do we go?
n / 2i £ 1 Þ
n £ 2i Þ
lg n £ i
| T (n) = n2 +
n2 /2 + n2/4 + ... + n2/ (2 lg n )
£ |
¥
n2 å
(1/2)k = 2n2
k
= 0 |
T (n) = Q ( n2)
Another example:
T (n) = T ( n/3 ) + T ( 2 n / 3 ) + n
| level1 |
|
|
n |
|
|
|
= n |
| level2 |
|
(n / 3) |
|
|
(2 n / 3) |
|
= n |
| level3 |
(n / 9) |
|
(2 n / 9) |
(2 n / 9) |
|
(4 n/9) |
= n |
The rows sum to n at every level -- but how many levels?
The left path: ( 1/3 )k n = 1
The right path: ( 2/3 )k n = 1 -- so we will use this longer
one
n = ( 3/2 )k Þ log3/2
n = k
T (n) £ n + n + n + ... + n {
log3/2 n times}
T (n) £ n log3/2
n = O ( n lg n )
|
