Algorithm Complexity I
Edson Ariel Ticona Zegarra
September 23, 2014
Exercise
Show that the solution of T (n) = T (n 1) + n is O(n2 )
By the iterative method:
T (n) = T (n 1) + n
= T (n 2) + n 1 + n
= T (n 3) + n 2 + n 1 + n
..
.
= T (1) + 1 + 2 + + n 2 + n 1 + n
n(n + 1)
=
2
Thus, T (n) = O(n2 )
Exercise
Show that the solution of T (n) = T (dn/2e) + 1 is O(lg n)
By the substitution method:
T (n) = O(lg n), T (n) c lg n b
T (n) = T (dn/2e) + 1 c lgdn/2e b + 1
c lg n b + 1
= c lg n (b 1) c lg n , for b 1 0
This holds for b 1, c > 0 and n > 0
Exercise
To prove that T (n) = 2T (bn/2c)+n is T (n) = (n lg n) the substitution method
can be used.
kcn lg n
k (n)j n
j nT
lg
+n
T (n) 2c
2
2
n1
n
2c
lg + n
2
4
= c(n 1)(lg n lg 4) + n
= cn lg n c lg n 2cn + 2c + n
= cn lg n + n(1 2c) c lg n cn lg n
|
{z
}
0 to hold the inequality
Then, T (n) = (n lg n) for 0 < c < 1/3 and n > 1
1
Note that the first step is important to get the result, this is straight forward
from the following fact:
jnk n 1
2k
2
jn
n
lg
lg
2
4
By multiplying the
positive
increasing functions:
jnk jnk
n1
n
lg
lg
2
2
2
4
The term needed is obtained.
Exercise
T (n) = 4T (n/2) + n
Assuming T (n) cn2
n 2
+n
T (n) 4c
2
= cn2 + n cn2
There is no n > 0 such that the last inequality remains true. Then, it is possible
to use a tightly lower bound like T (n) cn2 bn
n 2
n
b +n
T (n) 4c
2
2
b
2
= cn (n n) cn2
2
b
The last holds for n n 0. Then b 2 and n > 0.
2
Exercise
Expanding the recursion tree for T (n) = 3T (bn/2c) + n
n
PP
PP
?
)
q
P
b n2 c
b n2 c
b n2 c
lg n
@
?
R
@
@
?
R
@
- 3b n c
2
@
?@
R
b 2n2 cb 2n2 cb 2n2 cb 2n2 cb 2n2 cb 2n2 cb 2n2 cb 2n2 cb 2n2 c
..
.
?
..
.
..
.
..
.
..
.
..
.
..
.
..
.
..
.
T (1) T (1) T (1) T (1) T (1) T (1)
jnk
j n k
+ 32 2 + . . . + 3lg n lg n + (nlg 3 )
2 2
lg n 2
2
3
3
3
n+ n+
n + ... +
n + (nlg 3 )
2
2
2
lg n i
X
3
=n
2
i=0
T (n) = n + 3
=n
jnk
1 (3/2)lg n
= 2nlg 3 2n = O(nlg 3 )
1 3/2
2
- 32 b n2 c
2
..
.
- (nlg 3 )
So, the time complexity is T (n) = O(nlg 3 )
To verify this result by the substitution method, a function T (n) cnlg 3 bn
is choosen, solving:
n lg 3
T (n) = 3c
bn + n
2
lg 3
nlg 3
n
= 3c lg 3 bn + n = 3c
bn + n
2
3
= cnlg 3 (bn n) cnlg 3
Then, bn n 0 so this result holds for b 1 and n > 0
Exercise
Making the recursion tree for T (n) = T (n a) + T (a) + c n:
T (a) + cn
6
?
T (a) + c(n a)
n/a
?
T (a) + c(n 2a)
?
T (a) + c(n 3a)
..
.
T (1)
Summing all the elements in the tree:
n/a
X
n
T (n) = T (a) +
c(n i a)
a
i=0
n/a
n/a
X
X
n
= T (a) + c
na
i
a
i=0
i=0
n n
n
n
a ( a + 1)
= T (a) + c n a
a
a
2
n
cn2
cn
= T (a) +
a
2a
2
2
Hence, T (n) = O(n )
Exercise
T (n) = 4T (n/2) + n2 lg n
Checking the cases for the master theorem:
1st case: n2 lg n
/ O(nlg2 4 ) for > 0
2nd case: n2 lg n
/ O(nlg2 4 ) for > 0
3rd case: n2 lg n (nlg2 4+ )
4f (n/2) cf (n)
n2
4 (lg n 1) cn2 lg n
4
lg n 1 c lg n
There is no c < 1 such that the inequivalence can be fulfilled so the master
theorem can not be applied for this recurrence. The recursion tree method can
be used to the solve like this:
n2 lg n
6
?
4 n2 2 lg n2
lg n
?
lg
42 2n2 2
n
22
?
43 2n3 2 lg
..
.
n
23
T (1)
Adding:
lg n
X
n2 n
T (n) =
4i i lg i
2
2
i=0
lg n
X
n2
(lg n lg 2i )
2i
2
i=0
lg n
X
lg n(lg n + 1)
n2 2
n2
2
2
2
=n
(lg n i) = n lg n
=
lg n
lg n
2
2
2
i=0
=
22i
From the outcoming result, it is clear that T (n) = O(n2 lg2 n)
Exercise
T (n) = 2T (n/4) + 1
1st case: 1 O(nlog4 2 ) , for > 0
Then, T (n) = (n0.5 )
T (n) = 2T(n/4) + n
1st case: n
/ O(nlog4 2 ) , for > 0
nd
2 case: n O(nlog4 2 )
Then, T (n) = (nlog4 2 lgn) = ( n lg n)
T (n) = 2T (n/4) + n
1st case: n
/ O(nlog4 2 )
nd
2 case: n
/ O(nlog4 2 )
rd
3 case: n O(nlog4 2+ )
2f (n/4) c(f n)
n
cn
4
n
cn
2
Hence, T (n) = (n) for
2
1
2
c < 1 and n 0.
T (n) = 2T (n/4) + n2
1st case: n2
/ O(nlog4 2 )
2nd case: n2
/ O(nlog4 2 )
3rd case: n2 O(nlog4 2+ ), for = 1.5
2f (n/4) cn2
n 2
cn2
2
4
n2
cn2
8
Hence, T (n) = (n2 ) for 18 c < 1 and n 0
