Transcript PPT

Solutions to Recurrences
Supplementary Notes
Prepared by Raymond Wong
Presented by Raymond Wong
1
Is x greater than k (given by us)?
Is x equal to k (given by us)?
e.g.1 (Page 4)


Somebody has chosen a “hidden”
number x between 1 and n.
We want to discover x by asking one of
the following two types of questions.


Is x greater than k (given by us)?
Is x equal to k (given by us)?
2
Is x greater than k (given by us)?
Is x equal to k (given by us)?
e.g.1

When n = 1
1
We will ask:
is x equal to 1? Yes
Let T(n) be the total number of questions given n numbers.
T(n) = 1
3
Is x greater than k (given by us)?
Is x equal to k (given by us)?
e.g.1

When n = 2
Right number
Left number
1
2
We will ask:
is x greater than 1? Yes
Let T(n) be the total number of questions given n numbers.
T(n) = 1
4
Is x greater than k (given by us)?
Is x equal to k (given by us)?
e.g.1

When n = 2
Right number
Left number
1
2
We will ask:
is x greater than 1? Yes
is x equal to 2? Yes
Let T(n) be the total number of questions given n numbers.
T(n) = 12
5
Is x greater than k (given by us)?
Is x equal to k (given by us)?
e.g.1

When n is equal to any number
Right number set
Left number set
1
2
3
4
5
6
7
8
We will ask:
is x greater than 4? Yes
Let T(n) be the total number of questions given n numbers.
T(n) = 1
6
Is x greater than k (given by us)?
Is x equal to k (given by us)?
e.g.1

When n is equal to any number
Right number set
Left number set
1
2
3
4
5
6
7
8
We will ask:
is x greater than 4? Yes
Then, we ask a number of questions in the right number set
for n/2 numbers (i.e., 8/2 = 4 numbers)
The total number of questions in the right number set = T(n/2)
Let T(n) be the total number of questions given n numbers.
T(n) = 1 + T(n/2)
7
n
T(n) =
2T(2 ) + n if n > 1
T(1)
if n = 1
e.g.2 (Page 12)

Given
n
2
2T( ) + n
if n > 1
T(1)
if n = 1
find the closed form of T(n) by iterating
the recurrence
T(n) =
8
n
T(n) =
2T(2 ) + n if n > 1
T(1)
if n = 1
e.g.2
T(n)
n
n
=2T( 2 ) + n
=2( 2T( 22) + n ) + n
n
=22T(
=22( 2T( 23)
) + 2n
22
n
=23T( 23 )
n
2
n
+ 22)
n
=22T( 22 ) + n + n
n
+ 2n =23T( 23 ) + n + 2n
+ 3n
…
What should we do next?
n
=2iT( 2i ) + i.n
…
=2log
2
n
n
The base case is T(1). Thus, we want
2i = n
Thus, i = log2n
T( 2 log n) + (log2n) .n
2
=n T(1) + n log2n
Note that 2log2n = n
Since T(1) is equal to a constant (e.g., b),
T(n) = n.b + n log2n = (n log2n)
9
n
T(n) =
T( 2 ) + 1
if n  2
1
if n = 1
e.g.3 (Page 15)

Given
n
2
T( ) + 1
if n  2
1
if n = 1
find the closed form of T(n) by iterating
the recurrence
T(n) =
10
n
T(n) =
T( 2 ) + 1
if n  2
1
if n = 1
e.g.3
T(n)
n
n
=T(2 ) + 1
=( T( 22) + 1) + 1
n
=T( 22)
n
=T( 23)
=( T( 23) + 1) + 2
+2
n
+3
…
What should we do next?
n
=T( 2i ) + i
…
n
The base case is T(1). Thus, we want
2i = n
Thus, i = log2n
=T( 2 log n) + log2n
2
=T(1) + log2n
=1 + log2n
Note that 2log2n = n
T(n) = (log2n) = O(n)
11
n
T(n) =
T( 2 ) + n
if n  2
1
if n = 1
e.g.4 (Page 16)

Given
n
2
T( ) + n
if n  2
1
if n = 1
find the closed form of T(n) by iterating
the recurrence
T(n) =
12
n
T(n) =
T(n)
T( 2 ) + n
if n  2
1
if n = 1
e.g.4
=T( ) +
+n
n
n
=( T( 22) +
=T(2 ) + n
=T(
…
=T(
…
n
22
n
)
23
+
n
)
2i
+
n
2
n
22
n
2
+n
…
2log n-1+
2log2n-1
n
+
2log2n-2
n
+ n2
2
+
n
+…
2log2n-2
2
+n
What should we do next?
n
n
n
n
2
n
n
+
+
i-1
2
2i-2
=T( 2log n ) +
=T(1) +
+
n
=( T( 23 ) +
n
)+n
2
n
n
)
+
2
2
2
n
+
2
n
n
+ 22 +
n
+…
The base case is T(1). Thus, we want
2i = n
Thus, i = log2n
+ 22 +
n
+
2
n
+
2
+
2log2n-1
2log2n-2
2
2
= (n)
+
2
2
2
+…
Note that 2log2n = n
n
n
n
+
+n
2
2
2
n
n
n
n
n
= n + 2log n-1 + 2log n-2 + …
+ 22 + 2 + n
n
n
n
n
n
= 2log n + 2log n-1 + 2log n-2 + …
+22 + n + 20
2
1
1
1
1
1
=n( 2log n + 2log n-1 + 2log n-2 + … + 22 + 1 + 20
2
log2 n
=n  ( 1 )i
2
i 0
=1 +
n
By Lemma 4.3 or Theorem 4.4,
2
2
2
)
log2 n
 ( 21 )i = (t(n))
i 0
Since
r =1/2 (<1), t(n) = (1)
log n
 ( 21 )i = (1)
2
i 0
13
e.g.5 (Page 22)
This value (i.e.,2) is equal to 2.
e.g.2 (Page 12)
T(n) =
e.g.3 (Page 15)
T(n) =
e.g. 4 (Page 16)
T(n) =
n
2T(2 ) + n if n > 1
T(1)
n
if n = 1
T( 2 ) + 1
if n  2
1
if n = 1
T(n) = O(n)
This value (i.e.,1) is smaller than 2.
n
T( 2 ) + n
if n  2
T(n) = (n)
1
if n = 1
This value (i.e.,4) is larger than 2.
n
T(n) =
T(n) = (n log2n)
4T( 2 ) + n
if n  2
1
if n = 1
T(n) = ( ? )
It is equal to nlog 4=n2
2
14
If a > 2,
find the complexity of
(log2 n ) 1

i 0
a
( )i
2
e.g.6 (Page 25)

(log2 n ) 1
If a > 2,
a i
what is the complexity of  ( ) ?
2
i 0
15
If a > 2,
find the complexity of
(log2 n ) 1

i 0
a
( )i
2
e.g.6
We know the following lemma.
Lemma 4.3 (or Theorem 4.4): Let r  1 be a positive value independent of m.
Let t(m) be the largest term in the geometric series
m 1
 ri
i 0
Then, the value of the geometric series is (t(m)).
According to the explanation in our previous lecture,
if r < 1, t(m) = O(1)
The value of the geometric series is (1).
m-1
if r > 1, t(m) = O(r )
The value of the geometric series is (rm-1).
a
>1
Since a > 2,
2
a (log n)–1
Thus, t(m) = O( ( ) 2
)
2
a
The value of the geometric series is O( ( )(log2n)–1 )
(log n ) 1
2
a i
a (log n)–1
The complexity of  ( ) is O( ( ) 2 )
2
i 0
2
2
16