Analysis of Algorithms : An Active Learning Approach

36 ANALYSIS BASICS

by 2, each of the subsequent equations will have half the value. This gives us

the equations

Now, we again substitute back into the original giving the following series of

equations:

We notice that the coefficient of 
1 increases by a power of 4 each time we

substitute, and it is the case that the power of 2 that we divide n by is 1 greater

than the largest power of 4 for this coefficient. Also, we notice that the coeffi-

cient of T is the same power of 4 as the power of 2 that we divide n by. When

we have , its coefficient will be 4i and we will have terms from –(4i–1)

to –1. Now, for what value of i can we stop the substitution? Well, because we

Tn()⁄ 2 = 4 Tn()⁄ 4 – 1

Tn()⁄ 4 = 4 Tn()⁄ 8 – 1

Tn()⁄ 8 = 4 Tn()⁄ 16 – 1

Tn()⁄ 16 = 4 Tn()⁄ 32 – 1

Tn()⁄ 32 = 4 Tn()⁄ 64 – 1

Tn()== 4 Tn()⁄ 2 – 1 44 ()Tn()⁄ 4 – 1 – 1

Tn()= 16 Tn()⁄ 4 – (^4) 1 – 1
Tn()=16 4()Tn()⁄ 8 – 1 – (^4) 1 – 1
Tn()= 64 Tn()⁄ 8 – (^16) 1 – (^4) 1 – 1
Tn()=64 4()Tn()⁄ 16 – 1 – (^16) 1 – (^4) 1 – 1
Tn()= 256 Tn()⁄ 16 – (^64) 1 – (^16) 1 – (^4) 1 – 1
Tn()=256 4()Tn()⁄ 32 – 1 – (^64) 1 – (^16) 1 – (^4) 1 – 1
Tn()= 1024 Tn()⁄ 32 – (^256) 1 – (^64) 1 – (^16) 1 – (^4) 1 – 1
Tn()=1024 4()Tn()⁄ 64 – 1 – (^256) 1 – (^64) 1 – (^16) 1 – (^4) 1 – 1
Tn()= 4096 Tn()⁄ 64 – (^1024) 1 – (^256) 1 – (^64) 1 – (^16) 1 – (^4) * 1 – 1
Tn()⁄ 2 i