Recursion

Ali Alilooee

Recursive
problems
Substitution
method Recursion
Basic
recursive
algorithms
Recursion Ali Alilooee
trees method
Taught by: Greg Ryslik :)
Some Ohio State University
formulas for
recurrences
 Presentation Outline

Recursion

Ali Alilooee

Recursive 1 Recursive problems

problems
Substitution
method
2 Substitution method
Basic
recursive
algorithms
Recursion 3 Basic recursive algorithms
trees method
Some
formulas for
recurrences
4 Recursion trees method

5 Some formulas for recurrences

 Divide-and-Conquer

Recursion

Ali Alilooee
Question
Recursive
problems
How to solve a problem recursively?
Substitution
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Divide-and-Conquer

Recursion

Ali Alilooee
Question
Recursive
problems
How to solve a problem recursively?
Substitution
method
Basic
We solve a problem recursively by applying three following steps:
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Divide-and-Conquer

Recursion

Ali Alilooee
Question
Recursive
problems
How to solve a problem recursively?
Substitution
method
Basic
We solve a problem recursively by applying three following steps:
recursive
algorithms Divide the problem into a number of subproblems that are
Recursion smaller instances of the same problem.
trees method
Some
formulas for
recurrences
 Divide-and-Conquer

Recursion

Ali Alilooee
Question
Recursive
problems
How to solve a problem recursively?
Substitution
method
Basic
We solve a problem recursively by applying three following steps:
recursive
algorithms Divide the problem into a number of subproblems that are
Recursion smaller instances of the same problem.
trees method
Some
Conquer the subproblems by solving them recursively. If
formulas for
recurrences
the subproblem sizes are small enough, however, just solve
the subproblems in a straightforward manner.
 Divide-and-Conquer

Recursion

Ali Alilooee
Question
Recursive
problems
How to solve a problem recursively?
Substitution
method
Basic
We solve a problem recursively by applying three following steps:
recursive
algorithms Divide the problem into a number of subproblems that are
Recursion smaller instances of the same problem.
trees method
Some
Conquer the subproblems by solving them recursively. If
formulas for
recurrences
the subproblem sizes are small enough, however, just solve
the subproblems in a straightforward manner.
Combine the solutions to the subproblems into the
solution for the original problem.
 Merge sort (Sort 39, 27, 43, 3, 9, 82, 10)

Recursion 39 27 43 3 9 82 10
Ali Alilooee

Recursive 39 27 43 3 9 82 10
problems
Substitution
method
Basic
39 27 43 3 9 82 10
recursive
algorithms
Recursion
trees method
39 27 43 3 9 82 10
Some
formulas for
recurrences 27 39 3 43 9 82 10

3 27 39 43 9 10 82

3 9 10 27 39 43 82
 Presentation Outline

Recursion

Ali Alilooee

Recursive 1 Recursive problems

problems
Substitution
method
2 Substitution method
Basic
recursive
algorithms
Recursion 3 Basic recursive algorithms
trees method
Some
formulas for
recurrences
4 Recursion trees method

5 Some formulas for recurrences

 Recurrences

Recursion

Ali Alilooee

Recursive
problems
Substitution
A recurrence is an equation or inequality that describes a
method function in terms of its value on smaller inputs.
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Recurrences

Recursion

Ali Alilooee

Recursive
problems
Substitution
A recurrence is an equation or inequality that describes a
method function in terms of its value on smaller inputs.
Basic
recursive
For example the following recurrence.
algorithms

if n = 1
(
Recursion C  
trees method
T (n) = n (1)
Some 2T + Cn if n 6= 1
formulas for 2
recurrences
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion factorial(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(1) C
Recursive
problems 3: Else
Substitution 4: Return([Link](n − 1)) T (n − 1)
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion factorial(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(1) C
Recursive
problems 3: Else
Substitution 4: Return([Link](n − 1)) T (n − 1)
method
Then we have the recurrence T (n) = T (n − 1) + C , T (0) = C .
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion factorial(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(1) C
Recursive
problems 3: Else
Substitution 4: Return([Link](n − 1)) T (n − 1)
method
Then we have the recurrence T (n) = T (n − 1) + C , T (0) = C .
Basic
recursive
algorithms T (n − 1) = T (n − 2) + C =⇒ T (n) = T (n − 2) + C + C
Recursion
trees method
Some
formulas for
recurrences
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion factorial(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(1) C
Recursive
problems 3: Else
Substitution 4: Return([Link](n − 1)) T (n − 1)
method
Then we have the recurrence T (n) = T (n − 1) + C , T (0) = C .
Basic
recursive
algorithms T (n − 1) = T (n − 2) + C =⇒ T (n) = T (n − 2) + C + C
Recursion
trees method
T (n) = T (n − 2) + 2C
Some
formulas for
recurrences
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion factorial(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(1) C
Recursive
problems 3: Else
Substitution 4: Return([Link](n − 1)) T (n − 1)
method
Then we have the recurrence T (n) = T (n − 1) + C , T (0) = C .
Basic
recursive
algorithms T (n − 1) = T (n − 2) + C =⇒ T (n) = T (n − 2) + C + C
Recursion
trees method
T (n) = T (n − 2) + 2C
Some T (n − 2) = T (n − 3) + C =⇒ T (n) = T (n − 3) + C + 2C
formulas for
recurrences T (n) = T (n − 3) + 3C
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion factorial(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(1) C
Recursive
problems 3: Else
Substitution 4: Return([Link](n − 1)) T (n − 1)
method
Then we have the recurrence T (n) = T (n − 1) + C , T (0) = C .
Basic
recursive
algorithms T (n − 1) = T (n − 2) + C =⇒ T (n) = T (n − 2) + C + C
Recursion
trees method
T (n) = T (n − 2) + 2C
Some T (n − 2) = T (n − 3) + C =⇒ T (n) = T (n − 3) + C + 2C
formulas for
recurrences T (n) = T (n − 3) + 3C
...
T (n) = T (n − n) + nC
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion factorial(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(1) C
Recursive
problems 3: Else
Substitution 4: Return([Link](n − 1)) T (n − 1)
method
Then we have the recurrence T (n) = T (n − 1) + C , T (0) = C .
Basic
recursive
algorithms T (n − 1) = T (n − 2) + C =⇒ T (n) = T (n − 2) + C + C
Recursion
trees method
T (n) = T (n − 2) + 2C
Some T (n − 2) = T (n − 3) + C =⇒ T (n) = T (n − 3) + C + 2C
formulas for
recurrences T (n) = T (n − 3) + 3C
...
T (n) = T (n − n) + nC
T (n) = T (0) + nC = (n + 1)C
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion factorial(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(1) C
Recursive
problems 3: Else
Substitution 4: Return([Link](n − 1)) T (n − 1)
method
Then we have the recurrence T (n) = T (n − 1) + C , T (0) = C .
Basic
recursive
algorithms T (n − 1) = T (n − 2) + C =⇒ T (n) = T (n − 2) + C + C
Recursion
trees method
T (n) = T (n − 2) + 2C
Some T (n − 2) = T (n − 3) + C =⇒ T (n) = T (n − 3) + C + 2C
formulas for
recurrences T (n) = T (n − 3) + 3C
...
T (n) = T (n − n) + nC
T (n) = T (0) + nC = (n + 1)C
=⇒ T (n) ∈ Θ(n)
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion b(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(0) C
Recursive
problems 3: ElIf (n = 1) then
Substitution 4: Return(1) C
method
5: Else
Basic
recursive 6: Return(fib(n − 1) + fib(n − 2)) T (n − 1) + T (n − 2)
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion b(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(0) C
Recursive
problems 3: ElIf (n = 1) then
Substitution 4: Return(1) C
method
5: Else
Basic
recursive 6: Return(fib(n − 1) + fib(n − 2)) T (n − 1) + T (n − 2)
algorithms
Then we have the recurrence
Recursion
trees method T (n) = T (n − 1) + T (n − 2) + C , then T (n) ≥ 2T (n − 2).
Some
formulas for
recurrences
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion b(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(0) C
Recursive
problems 3: ElIf (n = 1) then
Substitution 4: Return(1) C
method
5: Else
Basic
recursive 6: Return(fib(n − 1) + fib(n − 2)) T (n − 1) + T (n − 2)
algorithms
Then we have the recurrence
Recursion
trees method T (n) = T (n − 1) + T (n − 2) + C , then T (n) ≥ 2T (n − 2).
Some
formulas for T (n − 2) ≥ 2T (n − 4) =⇒ T (n) ≥ 2(2T (n − 4))
recurrences
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion b(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(0) C
Recursive
problems 3: ElIf (n = 1) then
Substitution 4: Return(1) C
method
5: Else
Basic
recursive 6: Return(fib(n − 1) + fib(n − 2)) T (n − 1) + T (n − 2)
algorithms
Then we have the recurrence
Recursion
trees method T (n) = T (n − 1) + T (n − 2) + C , then T (n) ≥ 2T (n − 2).
Some
formulas for T (n − 2) ≥ 2T (n − 4) =⇒ T (n) ≥ 2(2T (n − 4))
recurrences
=⇒ T (n) ≥ 22 T (n − 4)
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion b(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(0) C
Recursive
problems 3: ElIf (n = 1) then
Substitution 4: Return(1) C
method
5: Else
Basic
recursive 6: Return(fib(n − 1) + fib(n − 2)) T (n − 1) + T (n − 2)
algorithms
Then we have the recurrence
Recursion
trees method T (n) = T (n − 1) + T (n − 2) + C , then T (n) ≥ 2T (n − 2).
Some
formulas for T (n − 2) ≥ 2T (n − 4) =⇒ T (n) ≥ 2(2T (n − 4))
recurrences
=⇒ T (n) ≥ 22 T (n − 4)
T (n − 4) ≥ 2T (n − 6) =⇒ T (n) ≥ 22 (2T (n − 6))
=⇒ T (n) ≥ 23 (T (n − 6))
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion b(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(0) C
Recursive
problems 3: ElIf (n = 1) then
Substitution 4: Return(1) C
method
5: Else
Basic
recursive 6: Return(fib(n − 1) + fib(n − 2)) T (n − 1) + T (n − 2)
algorithms
Then we have the recurrence
Recursion
trees method T (n) = T (n − 1) + T (n − 2) + C , then T (n) ≥ 2T (n − 2).
Some
formulas for T (n − 2) ≥ 2T (n − 4) =⇒ T (n) ≥ 2(2T (n − 4))
recurrences
=⇒ T (n) ≥ 22 T (n − 4)
T (n − 4) ≥ 2T (n − 6) =⇒ T (n) ≥ 22 (2T (n − 6))
=⇒ T (n) ≥ 23 (T (n − 6))
...
T (n) ≥ 2k (T (n − 2k))
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion b(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(0) C
Recursive
problems 3: ElIf (n = 1) then
Substitution 4: Return(1) C
method
5: Else
Basic
recursive 6: Return(fib(n − 1) + fib(n − 2)) T (n − 1) + T (n − 2)
algorithms
Then we have the recurrence
Recursion
trees method T (n) = T (n − 1) + T (n − 2) + C , then T (n) ≥ 2T (n − 2).
Some
formulas for T (n − 2) ≥ 2T (n − 4) =⇒ T (n) ≥ 2(2T (n − 4))
recurrences
=⇒ T (n) ≥ 22 T (n − 4)
T (n − 4) ≥ 2T (n − 6) =⇒ T (n) ≥ 22 (2T (n − 6))
=⇒ T (n) ≥ 23 (T (n − 6))
...
T (n) ≥ 2k (T (n − 2k))
 Find the asymptotic worst-case running time (T (n))
of the following function.

Recursion b(n) Frequency

Ali Alilooee 1: If (n = 0) then
2: Return(0) C
Recursive
problems 3: ElIf (n = 1) then
Substitution 4: Return(1) C
method
5: Else
Basic
recursive 6: Return(fib(n − 1) + fib(n − 2)) T (n − 1) + T (n − 2)
algorithms
Then we have the recurrence
Recursion
trees method T (n) = T (n − 1) + T (n − 2) + C , then T (n) ≥ 2T (n − 2).
Some
formulas for T (n − 2) ≥ 2T (n − 4) =⇒ T (n) ≥ 2(2T (n − 4))
recurrences
=⇒ T (n) ≥ 22 T (n − 4)
T (n − 4) ≥ 2T (n − 6) =⇒ T (n) ≥ 22 (2T (n − 6))
=⇒ T (n) ≥ 23 (T (n − 6))
...
T (n) ≥ 2k (T (n − 2k))
 At least exponential

Recursion
Then we have
Ali Alilooee T (n) ≥ 2k (T (n − 2k)
Recursive
problems
Substitution
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 At least exponential

Recursion
Then we have
Ali Alilooee T (n) ≥ 2k (T (n − 2k)
Recursive
problems
Substitution The question is how much more we can continue this
method
Basic
process.
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 At least exponential

Recursion
Then we have
Ali Alilooee T (n) ≥ 2k (T (n − 2k)
Recursive
problems
Substitution The question is how much more we can continue this
method
Basic
process.
recursive
algorithms We continue this process until n − 2k gets zero.
Recursion
trees method
Some
formulas for
recurrences
 At least exponential

Recursion
Then we have
Ali Alilooee T (n) ≥ 2k (T (n − 2k)
Recursive
problems
Substitution The question is how much more we can continue this
method
Basic
process.
recursive
algorithms We continue this process until n − 2k gets zero.
Recursion Then we have
trees method
Some n
formulas for n − 2k = 0 =⇒ k = .
recurrences 2
 At least exponential

Recursion
Then we have
Ali Alilooee T (n) ≥ 2k (T (n − 2k)
Recursive
problems
Substitution The question is how much more we can continue this
method
Basic
process.
recursive
algorithms We continue this process until n − 2k gets zero.
Recursion Then we have
trees method
Some n
formulas for n − 2k = 0 =⇒ k = .
recurrences 2

Then since T (0) = C we have T (n) ≥ C 2n/2 and so

 At least exponential

Recursion
Then we have
Ali Alilooee T (n) ≥ 2k (T (n − 2k)
Recursive
problems
Substitution The question is how much more we can continue this
method
Basic
process.
recursive
algorithms We continue this process until n − 2k gets zero.
Recursion Then we have
trees method
Some n
formulas for n − 2k = 0 =⇒ k = .
recurrences 2

Then since T (0) = C we have T (n) ≥ C 2n/2 and so

T (n) ∈ Ω(2n ).
 Find the asympthotic running time

Recursion
Input: Array A of n elements.
Ali Alilooee
procedure func(A, n)
Recursive
problems
1: if (n ≤ 20) then return (A[n]);
Substitution
2: end if
method 3: for i ← 1 to bn/2c do
Basic
recursive 4: A[i] ← A[i] + A[2 ∗ i];
algorithms
5: end for  
3n

Recursion
trees method 6: x ← func A, ;
Some
5
formulas for
recurrences
 Find the asympthotic running time

Recursion
Input: Array A of n elements.
Ali Alilooee
procedure func(A, n)
Recursive
problems
1: if (n ≤ 20) then return (A[n]);
Substitution
2: end if
method 3: for i ← 1 to bn/2c do
Basic
recursive 4: A[i] ← A[i] + A[2 ∗ i];
algorithms
5: end for  
3n

Recursion
trees method 6: x ← func A, ;
Some
5
formulas for
recurrences
We need tondthe asymptotic behavior of the recurrence
3n
T (n) = T + Cn.
5
 Find the asympthotic running time

Recursion
Input: Array A of n elements.
Ali Alilooee
procedure func(A, n)
Recursive
problems
1: if (n ≤ 20) then return (A[n]);
Substitution
2: end if
method 3: for i ← 1 to bn/2c do
Basic
recursive 4: A[i] ← A[i] + A[2 ∗ i];
algorithms
5: end for  
3n

Recursion
trees method 6: x ← func A, ;
Some
5
formulas for
recurrences
We need tondthe asymptotic behavior of the recurrence
3n
T (n) = T + Cn. Remember
5

3n 32 n 3
   
T =T + (Cn).
5 52 5
 Recursion Then we have
 2 
3n 3 n 3
 
Ali Alilooee
T (n) = T + Cn = T 2
+ (Cn) + Cn
Recursive
5 5 5
 3 
problems
3 n 32 3
Substitution = T + (Cn) + (Cn) + Cn
method 53 52 5
Basic ..
recursive
algorithms
.
k−1  i
3 n 3
 k 
Recursion
X
trees method = T + Cn
5 k
i=0
5
Some
formulas for
recurrences
 Recursion Then we have
 2 
3n 3 n 3
 
Ali Alilooee
T (n) = T + Cn = T 2
+ (Cn) + Cn
Recursive
5 5 5
 3 
problems
3 n 32 3
Substitution = T + (Cn) + (Cn) + Cn
method 53 52 5
Basic ..
recursive
algorithms
.
k−1  i
3 n 3
 k 
Recursion
X
trees method = T + Cn
5 k
i=0
5
Some
formulas for
recurrences we should continue this process until we reach to k for which
we have
3 1 3
 k  k
n=1⇒ =
5 n 5
 Recursion Then we have
 2 
3n 3 n 3
 
Ali Alilooee
T (n) = T + Cn = T 2
+ (Cn) + Cn
Recursive
5 5 5
 3 
problems
3 n 32 3
Substitution = T + (Cn) + (Cn) + Cn
method 53 52 5
Basic ..
recursive
algorithms
.
k−1  i
3 n 3
 k 
Recursion
X
trees method = T + Cn
5 k
i=0
5
Some
formulas for
recurrences we should continue this process until we reach to k for which
we have
3 1 3
 k  k
n=1⇒ =
5 n 5
3
 i
Pk−1
T (n) = T (1) + Cn i=0 =
5
 Recursion Then we have
 2 
3n 3 n 3
 
Ali Alilooee
T (n) = T + Cn = T 2
+ (Cn) + Cn
Recursive
5 5 5
 3 
problems
3 n 32 3
Substitution = T + (Cn) + (Cn) + Cn
method 53 52 5
Basic ..
recursive
algorithms
.
k−1  i
3 n 3
 k 
Recursion
X
trees method = T + Cn
5 k
i=0
5
Some
formulas for
recurrences we should continue this process until we reach to k for which
we have
3 1 3
 k  k
n=1⇒ =
5 n 5
3 3
 i  i
Pk−1 Pk−1
T (n) = T (1) + Cn i=0 = C + Cn i=0 .
5 5
 Recursion
Then we have
Ali Alilooee

Recursive
problems
Substitution
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Recursion
Then we have
Ali Alilooee
 2  k−1
3 3 3
 
Recursive T (n) = Cn + Cn + Cn + · · · + Cn + C
problems 5 5 5
Substitution
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Recursion
Then we have
Ali Alilooee
 2  k−1
3 3 3
 
Recursive T (n) = Cn + Cn + Cn + · · · + Cn + C
problems 5 5 5
Substitution  2  k−1 !
method 3 3 3 1
 
= Cn 1 + + + ··· + +
Basic
recursive 5 5 5 n
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Recursion
Then we have
Ali Alilooee
 2  k−1
3 3 3
 
Recursive T (n) = Cn + Cn + Cn + · · · + Cn + C
problems 5 5 5
Substitution  2  k−1 !
method 3 3 3 1
 
= Cn 1 + + + ··· + +
Basic
recursive 5 5 5 n
algorithms
 2  k−1  k !
3 3 3 3
 
Recursion
trees method = Cn 1 + + + ··· + +
Some
5 5 5 5
formulas for
recurrences
 Recursion
Then we have
Ali Alilooee
 2  k−1
3 3 3
 
Recursive T (n) = Cn + Cn + Cn + · · · + Cn + C
problems 5 5 5
Substitution  2  k−1 !
method 3 3 3 1
 
= Cn 1 + + + ··· + +
Basic
recursive 5 5 5 n
algorithms
 2  k−1  k !
3 3 3 3
 
Recursion
trees method = Cn 1 + + + ··· + +
Some
5 5 5 5
formulas for
k  i
recurrences X 3
= Cn
i=0
5
 Recursion
Then we have
Ali Alilooee
 2  k−1
3 3 3
 
Recursive T (n) = Cn + Cn + Cn + · · · + Cn + C
problems 5 5 5
Substitution  2  k−1 !
method 3 3 3 1
 
= Cn 1 + + + ··· + +
Basic
recursive 5 5 5 n
algorithms
 2  k−1  k !
3 3 3 3
 
Recursion
trees method = Cn 1 + + + ··· + +
Some
5 5 5 5
formulas for
k  i ∞  i
recurrences X 3 X 3
= Cn < Cn
i=0
5 i=0
5
 Recursion
Then we have
Ali Alilooee
 2  k−1
3 3 3
 
Recursive T (n) = Cn + Cn + Cn + · · · + Cn + C
problems 5 5 5
Substitution  2  k−1 !
method 3 3 3 1
 
= Cn 1 + + + ··· + +
Basic
recursive 5 5 5 n
algorithms
 2  k−1  k !
3 3 3 3
 
Recursion
trees method = Cn 1 + + + ··· + +
Some
5 5 5 5
formulas for
k  i ∞  i
recurrences
3 3 5
X X  
= Cn < Cn = Cn
i=0
5 i=0
5 2
 Recursion
Then we have
Ali Alilooee
 2  k−1
3 3 3
 
Recursive T (n) = Cn + Cn + Cn + · · · + Cn + C
problems 5 5 5
Substitution  2  k−1 !
method 3 3 3 1
 
= Cn 1 + + + ··· + +
Basic
recursive 5 5 5 n
algorithms
 2  k−1  k !
3 3 3 3
 
Recursion
trees method = Cn 1 + + + ··· + +
Some
5 5 5 5
formulas for
k  i ∞  i
recurrences
3 3 5
X X  
= Cn < Cn = Cn
i=0
5 i=0
5 2

5
 
Then Cn < T (n) < Cn
2
 Recursion
Then we have
Ali Alilooee
 2  k−1
3 3 3
 
Recursive T (n) = Cn + Cn + Cn + · · · + Cn + C
problems 5 5 5
Substitution  2  k−1 !
method 3 3 3 1
 
= Cn 1 + + + ··· + +
Basic
recursive 5 5 5 n
algorithms
 2  k−1  k !
3 3 3 3
 
Recursion
trees method = Cn 1 + + + ··· + +
Some
5 5 5 5
formulas for
k  i ∞  i
recurrences
3 3 5
X X  
= Cn < Cn = Cn
i=0
5 i=0
5 2

5
 
Then Cn < T (n) < Cn =⇒ T (n) ∈ Θ(n).
2
 Extra Extra Credits

Recursion

Ali Alilooee

Recursive
problems
3
 
Substitution
method Let T (n) = T n + Cn and T (1) = C , use the
5
Basic
recursive mathematical induction and show
algorithms
5
 
Recursion
trees method T (n) ≤ Cn, for all n ≥ 1.
2
Some
formulas for
recurrences
 Find the asympthotic running time

Recursion Input: Array A of n elements.

Ali Alilooee procedure func(A, n)
Recursive 1: if (n ≤ 10) then return (A[n]);
problems
2: end if
3: for i ← 1 to bn/2c do
Substitution
method
Basic 4: j ← 7;
recursive
algorithms 5: while (j ≤ bn/2c ) do
Recursion 6: A[i] ← A[i] + A[i + j];
trees method
7: j ← 5 ∗ j;
Some
formulas for 8: end while
recurrences
9: end for
10: x ← func (A, n − 8);
 Find the asympthotic running time

Recursion Input: Array A of n elements.

Ali Alilooee procedure func(A, n)
Recursive 1: if (n ≤ 10) then return (A[n]);
problems
2: end if
3: for i ← 1 to bn/2c do
Substitution
method
Basic 4: j ← 7;
recursive
algorithms 5: while (j ≤ bn/2c ) do
Recursion 6: A[i] ← A[i] + A[i + j];
trees method
7: j ← 5 ∗ j;
Some
formulas for 8: end while
recurrences
9: end for
10: x ← func (A, n − 8);
We need to nd the running time of the While loop (denoted by
k ). We have the following
n
7(5k ) = =⇒ k = log5 n/14 ≈ log n.
2
 Recursion Then since the running time of the For loop is n we have the
Ali Alilooee following recurrence for the function
Recursive T (n) = T (n − 8) + Cn log n
problems
Substitution
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Recursion Then since the running time of the For loop is n we have the
Ali Alilooee following recurrence for the function
Recursive T (n) = T (n − 8) + Cn log n ⇒
problems
Substitution
T (n − 8) = T (n − 16) + C (n − 8) log (n − 8).
method
Basic Then we have
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Recursion Then since the running time of the For loop is n we have the
Ali Alilooee following recurrence for the function
Recursive T (n) = T (n − 8) + Cn log n ⇒
problems
Substitution
T (n − 8) = T (n − 16) + C (n − 8) log (n − 8).
method
Basic Then we have
recursive
algorithms
T (n) = T (n − 8) + Cn log n
Recursion
trees method =
Some
formulas for
recurrences
 Recursion Then since the running time of the For loop is n we have the
Ali Alilooee following recurrence for the function
Recursive T (n) = T (n − 8) + Cn log n ⇒
problems
Substitution
T (n − 8) = T (n − 16) + C (n − 8) log (n − 8).
method
Basic Then we have
recursive
algorithms
T (n) = T (n − 8) + Cn log n
Recursion
trees method = T (n − 16) + C (n − 8) log (n − 8) + Cn log n
Some
formulas for =
recurrences
 Recursion Then since the running time of the For loop is n we have the
Ali Alilooee following recurrence for the function
Recursive T (n) = T (n − 8) + Cn log n ⇒
problems
Substitution
T (n − 8) = T (n − 16) + C (n − 8) log (n − 8).
method
Basic Then we have
recursive
algorithms
T (n) = T (n − 8) + Cn log n
Recursion
trees method = T (n − 16) + C (n − 8) log (n − 8) + Cn log n
Some
formulas for = T (n − 24) + C (n − 16) log (n − 16)
recurrences
+C (n − 8) log (n − 8) + Cn log n
..
.
 Recursion Then since the running time of the For loop is n we have the
Ali Alilooee following recurrence for the function
Recursive T (n) = T (n − 8) + Cn log n ⇒
problems
Substitution
T (n − 8) = T (n − 16) + C (n − 8) log (n − 8).
method
Basic Then we have
recursive
algorithms
T (n) = T (n − 8) + Cn log n
Recursion
trees method = T (n − 16) + C (n − 8) log (n − 8) + Cn log n
Some
formulas for = T (n − 24) + C (n − 16) log (n − 16)
recurrences
+C (n − 8) log (n − 8) + Cn log n
..
.
k−1
= T (n − 8k) + C (n − 8i) log (n − 8i)
X

i=0
 Recursion We continue this process until n − 8k = 0 and then k = n8 .
Ali Alilooee Remember that T (0) = C , then we have
Recursive k−1
problems
(n − 8i) log (n − 8i)
X
T (n) = C + C
Substitution
method i=0
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Recursion We continue this process until n − 8k = 0 and then k = n8 .
Ali Alilooee Remember that T (0) = C , then we have
Recursive k−1 k−1
problems
(n − 8i) log (n − 8i) < Cn log n + C
X X
T (n) = C + C n log n
Substitution
method i=0 i=0
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Recursion We continue this process until n − 8k = 0 and then k = n8 .
Ali Alilooee Remember that T (0) = C , then we have
Recursive k−1 k−1
problems
(n − 8i) log (n − 8i) < Cn log n + C
X X
T (n) = C + C n log n
Substitution
method i=0 i=0
Basic k
recursive
X
algorithms =⇒ T (n) < n log n
Recursion i=0
trees method
Some
formulas for
recurrences
 Recursion We continue this process until n − 8k = 0 and then k = n8 .
Ali Alilooee Remember that T (0) = C , then we have
Recursive k−1 k−1
problems
(n − 8i) log (n − 8i) < Cn log n + C
X X
T (n) = C + C n log n
Substitution
method i=0 i=0
Basic k
recursive
n log n = (k + 1)(n log n)
X
algorithms =⇒ T (n) <
Recursion i=0
trees method
Some
formulas for
recurrences
 Recursion We continue this process until n − 8k = 0 and then k = n8 .
Ali Alilooee Remember that T (0) = C , then we have
Recursive k−1 k−1
problems
(n − 8i) log (n − 8i) < Cn log n + C
X X
T (n) = C + C n log n
Substitution
method i=0 i=0
Basic k n 
recursive
n log n = (k + 1)(n log n) = + 1 (n log n)
X
algorithms =⇒ T (n) <
8
Recursion i=0
trees method
Some
formulas for
recurrences
 Recursion We continue this process until n − 8k = 0 and then k = n8 .
Ali Alilooee Remember that T (0) = C , then we have
Recursive k−1 k−1
problems
(n − 8i) log (n − 8i) < Cn log n + C
X X
T (n) = C + C n log n
Substitution
method i=0 i=0
Basic k n 
recursive
n log n = (k + 1)(n log n) = + 1 (n log n)
X
algorithms =⇒ T (n) <
8
Recursion i=0
trees method
n2
n   
Some =⇒ T (n) < + 1 (n log n) ≈ log n.
formulas for 8 8
recurrences
 Recursion We continue this process until n − 8k = 0 and then k = n8 .
Ali Alilooee Remember that T (0) = C , then we have
Recursive k−1 k−1
problems
(n − 8i) log (n − 8i) < Cn log n + C
X X
T (n) = C + C n log n
Substitution
method i=0 i=0
Basic k n 
recursive
n log n = (k + 1)(n log n) = + 1 (n log n)
X
algorithms =⇒ T (n) <
8
Recursion i=0
trees method
n2
n   
Some =⇒ T (n) < + 1 (n log n) ≈ log n.
formulas for 8 8
recurrences

To nd the lower bound we need to observe that

k−1
(n−8i) log (n − 8i)
X
T (n) = C +C
i=0
 Recursion We continue this process until n − 8k = 0 and then k = n8 .
Ali Alilooee Remember that T (0) = C , then we have
Recursive k−1 k−1
problems
(n − 8i) log (n − 8i) < Cn log n + C
X X
T (n) = C + C n log n
Substitution
method i=0 i=0
Basic k n 
recursive
n log n = (k + 1)(n log n) = + 1 (n log n)
X
algorithms =⇒ T (n) <
8
Recursion i=0
trees method
n2
n   
Some =⇒ T (n) < + 1 (n log n) ≈ log n.
formulas for 8 8
recurrences

To nd the lower bound we need to observe that

k−1 n/8
(n−8i) log (n − 8i) > C (n−8i) log (n − 8i)
X X
T (n) = C +C
i=0 i=n/16
 Recursion Then we have
Ali Alilooee n/8
(n − 8i) log (n − 8i)
X
T (n) > C
Recursive
problems i=n/16
Substitution
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Recursion Then we have
Ali Alilooee n/8
(n − 8i) log (n − 8i)
X
T (n) > C
Recursive
problems i=n/16
Substitution n/8
method
(n − 8(n/16)) log (n − 8(n/16))
X
Basic > C
recursive i=n/16
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Recursion Then we have
Ali Alilooee n/8
(n − 8i) log (n − 8i)
X
T (n) > C
Recursive
problems i=n/16
Substitution n/8
method
(n − 8(n/16)) log (n − 8(n/16))
X
Basic > C
recursive i=n/16
algorithms
Recursion n/8
trees method
(n − (n/2)) log (n − (n/2))
X
=
Some
formulas for i=n/16
recurrences
 Recursion Then we have
Ali Alilooee n/8
(n − 8i) log (n − 8i)
X
T (n) > C
Recursive
problems i=n/16
Substitution n/8
method
(n − 8(n/16)) log (n − 8(n/16))
X
Basic > C
recursive i=n/16
algorithms
Recursion n/8
trees method
(n − (n/2)) log (n − (n/2))
X
=
Some
formulas for i=n/16
recurrences
n/8  n  n n
(n/2) log (n/2) =
X
= log
16 2 2
i=n/16

n2 n2
 
≈ log n ⇒ T (n) > log n ⇒ T (n) ∈ Θ(n2 log n).
32 32
 Extra Extra Credits

Recursion

Ali Alilooee

Recursive
problems
Substitution
method Let T (n) = T (n − 8) + Cn log n, for n > 8 and T (0) = C . Use
Basic the mathematical induction and show
recursive
algorithms
C C
Recursion n2 log n ≤ T (n) ≤ n2 log n, for all n ≥ 8.
trees method 64 8
Some
formulas for
recurrences
 Presentation Outline

Recursion

Ali Alilooee

Recursive 1 Recursive problems

problems
Substitution
method
2 Substitution method
Basic
recursive
algorithms
Recursion 3 Basic recursive algorithms
trees method
Some
formulas for
recurrences
4 Recursion trees method

5 Some formulas for recurrences

 Recursive algorithm for selection sort

Recursion
Input: Array A of n elements.
Ali Alilooee
Result: Permutation of A such that
Recursive
problems
Substitution
A[1] ≤ A[2] ≤ · · · ≤ A[n].
method
Basic
recursive
procedure SelectionSort(A[], n)
algorithms 1: if (n ≤ 1) then return ;
Recursion
trees method 2: else
Some 3: for i ← 1 to n − 1 do
formulas for
recurrences 4: if (A[i] > A[n]) then
5: Swap(A[i], A[n]);
6: end if
7: end for
8: SelectionSort(A[], n − 1);
9: end if
 Find asymptotic worst-case running time of the
SelectionSort.

Recursion Since the running time of the For loop is Cn then we have the
Ali Alilooee recurrence T (n) = T (n − 1) + Cn. Then we have
Recursive
problems
Substitution
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Find asymptotic worst-case running time of the
SelectionSort.

Recursion Since the running time of the For loop is Cn then we have the
Ali Alilooee recurrence T (n) = T (n − 1) + Cn. Then we have
Recursive T (n) = T (n − 1) + Cn =
problems
Substitution
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Find asymptotic worst-case running time of the
SelectionSort.

Recursion Since the running time of the For loop is Cn then we have the
Ali Alilooee recurrence T (n) = T (n − 1) + Cn. Then we have
Recursive T (n) = T (n − 1) + Cn = T (n − 2) + C (n − 1) + Cn
problems
Substitution
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Find asymptotic worst-case running time of the
SelectionSort.

Recursion Since the running time of the For loop is Cn then we have the
Ali Alilooee recurrence T (n) = T (n − 1) + Cn. Then we have
Recursive T (n) = T (n − 1) + Cn = T (n − 2) + C (n − 1) + Cn
problems
2
Substitution
= T (n − 3) +
X
method C (n − i)
Basic i=0
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Find asymptotic worst-case running time of the
SelectionSort.

Recursion Since the running time of the For loop is Cn then we have the
Ali Alilooee recurrence T (n) = T (n − 1) + Cn. Then we have
Recursive T (n) = T (n − 1) + Cn = T (n − 2) + C (n − 1) + Cn
problems
2
Substitution
= T (n − 3) +
X
method C (n − i)
Basic i=0
recursive
algorithms ..
.
Recursion
trees method = T (n − n) + C (n − (n − 1)) +
Some
formulas for
recurrences
 Find asymptotic worst-case running time of the
SelectionSort.

Recursion Since the running time of the For loop is Cn then we have the
Ali Alilooee recurrence T (n) = T (n − 1) + Cn. Then we have
Recursive T (n) = T (n − 1) + Cn = T (n − 2) + C (n − 1) + Cn
problems
2
Substitution
= T (n − 3) +
X
method C (n − i)
Basic i=0
recursive
algorithms ..
.
Recursion
trees method = T (n − n) + C (n − (n − 1)) +
Some
formulas for · · · + C (n − 1) + Cn
recurrences
 Find asymptotic worst-case running time of the
SelectionSort.

Recursion Since the running time of the For loop is Cn then we have the
Ali Alilooee recurrence T (n) = T (n − 1) + Cn. Then we have
Recursive T (n) = T (n − 1) + Cn = T (n − 2) + C (n − 1) + Cn
problems
2
Substitution
= T (n − 3) +
X
method C (n − i)
Basic i=0
recursive
algorithms ..
.
Recursion
trees method = T (n − n) + C (n − (n − 1)) +
Some
formulas for · · · + C (n − 1) + Cn
recurrences
n−1
= T (0) + C
X
(n − i)
i=0
 Find asymptotic worst-case running time of the
SelectionSort.

Recursion Since the running time of the For loop is Cn then we have the
Ali Alilooee recurrence T (n) = T (n − 1) + Cn. Then we have
Recursive T (n) = T (n − 1) + Cn = T (n − 2) + C (n − 1) + Cn
problems
2
Substitution
= T (n − 3) +
X
method C (n − i)
Basic i=0
recursive
algorithms ..
.
Recursion
trees method = T (n − n) + C (n − (n − 1)) +
Some
formulas for · · · + C (n − 1) + Cn
recurrences
n−1
= T (0) + C
X
(n − i)
i=0
n−
X 1
= C +C (n − i)
i=0
 Find asymptotic worst-case running time of the
SelectionSort.

Recursion Since the running time of the For loop is Cn then we have the
Ali Alilooee recurrence T (n) = T (n − 1) + Cn. Then we have
Recursive T (n) = T (n − 1) + Cn = T (n − 2) + C (n − 1) + Cn
problems
2
Substitution
= T (n − 3) +
X
method C (n − i)
Basic i=0
recursive
algorithms ..
.
Recursion
trees method = T (n − n) + C (n − (n − 1)) +
Some
formulas for · · · + C (n − 1) + Cn
recurrences
n−1
= T (0) + C
X
(n − i)
i=0
n− 1 n
Cn = Cn2
X X
= C +C (n − i) ≤
i=0 i=0
 Recursion

Ali Alilooee

Recursive
Then
problems =⇒ T (n) ∈ O(n2 ).
Substitution
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Recursion

Ali Alilooee

Recursive
Then
problems =⇒ T (n) ∈ O(n2 ).
Substitution
method Note that since we have
Basic
recursive n−1
algorithms X n
T (n) = C + C (n − i) ≥ C ( ) + · · · + C (n)
Recursion
trees method
2
i=0
Some
formulas for
recurrences
 Recursion

Ali Alilooee

Recursive
Then
problems =⇒ T (n) ∈ O(n2 ).
Substitution
method Note that since we have
Basic
recursive n−1
algorithms X n
T (n) = C + C (n − i) ≥ C ( ) + · · · + C (n)
Recursion
trees method
2
i=0
Some
formulas for n n n
recurrences ≥ C( ) + C( ) + · · · + C( )
2 2 2
 Recursion

Ali Alilooee

Recursive
Then
problems =⇒ T (n) ∈ O(n2 ).
Substitution
method Note that since we have
Basic
recursive n−1
algorithms X n
T (n) = C + C (n − i) ≥ C ( ) + · · · + C (n)
Recursion
trees method
2
i=0
Some
formulas for n n n Cn2
recurrences ≥ C( ) + C( ) + · · · + C( ) =
2 2 2 4
 Recursion

Ali Alilooee

Recursive
Then
problems =⇒ T (n) ∈ O(n2 ).
Substitution
method Note that since we have
Basic
recursive n−1
algorithms X n
T (n) = C + C (n − i) ≥ C ( ) + · · · + C (n)
Recursion
trees method
2
i=0
Some
formulas for n n n Cn2
recurrences ≥ C( ) + C( ) + · · · + C( ) =
2 2 2 4
Then T (n) ∈ Θ(n2 ).
 Binary Search: Recursive Version

Recursion Input: p such that (A[p] = K and i ≤ p ≤ j ) or 0 if K is

Ali Alilooee not in the array
Recursive
function BinarySearchRec (A[], i, j, K )
problems
1: if (i ≤ j ) then
Substitution
method 2: midp ← b(i + j)/2c;
Basic 3: if (K = A[midp]) then index ← midp ;
recursive
algorithms 4: else if (K < A[midp]) then
Recursion 5:
trees method
index ← BinarySearchRec(A, i, midp − 1, K );
Some
formulas for 6: else/*K > A[midp] */
recurrences
7:
index ← BinarySearchRec(A, midp + 1, j, K );
8: end if
9: return (index );
10: else
11: return (0);
 Find asymptotic worst-case running time of the
BinarySearchRec.

Recursion Since the running time of the assignment

 nof midp is constant
Ali Alilooee then we have the recurrence T (n) = T + C . Then since
n n 2
Recursive
problems T =T + C we have
2 4
Substitution
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Find asymptotic worst-case running time of the
BinarySearchRec.

Recursion Since the running time of the assignment

 nof midp is constant
Ali Alilooee then we have the recurrence T (n) = T + C . Then since
n n 2
Recursive
problems T =T + C we have
2 4
Substitution n
method
T (n) = T +C =
Basic 2
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Find asymptotic worst-case running time of the
BinarySearchRec.

Recursion Since the running time of the assignment

 nof midp is constant
Ali Alilooee then we have the recurrence T (n) = T + C . Then since
n n 2
Recursive
problems T =T + C we have
2 4
Substitution n n n
method
T (n) = T +C = T +C +C =T + 2C
Basic 2 4 4
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Find asymptotic worst-case running time of the
BinarySearchRec.

Recursion Since the running time of the assignment

 nof midp is constant
Ali Alilooee then we have the recurrence T (n) = T + C . Then since
n n 2
Recursive
problems T =T + C we have
2 4
Substitution n n n
method
T (n) = T +C = T +C +C =T + 2C
Basic 2  n4  4
recursive
algorithms = T + 3C
Recursion
8
trees method
Some
formulas for
recurrences
 Find asymptotic worst-case running time of the
BinarySearchRec.

Recursion Since the running time of the assignment

 nof midp is constant
Ali Alilooee then we have the recurrence T (n) = T + C . Then since
n n 2
Recursive
problems T =T + C we have
2 4
Substitution n n n
method
T (n) = T +C = T +C +C =T + 2C
Basic 2  n4  4
recursive
algorithms = T + 3C
Recursion
8
trees method ..
Some
. n
formulas for
recurrences = T + kC
2k
 Find asymptotic worst-case running time of the
BinarySearchRec.

Recursion Since the running time of the assignment

 nof midp is constant
Ali Alilooee then we have the recurrence T (n) = T + C . Then since
n n 2
Recursive
problems T =T + C we have
2 4
Substitution n n n
method
T (n) = T +C = T +C +C =T + 2C
Basic 2  n4  4
recursive
algorithms = T + 3C
Recursion
8
trees method ..
Some
. n
formulas for
recurrences = T + kC
2k
n
We continue this process until we reach to = 1 and then
2k
n= 2k =⇒ k = log n. So we have T (n) = T (1) + kC
 Find asymptotic worst-case running time of the
BinarySearchRec.

Recursion Since the running time of the assignment

 nof midp is constant
Ali Alilooee then we have the recurrence T (n) = T + C . Then since
n n 2
Recursive
problems T =T + C we have
2 4
Substitution n n n
method
T (n) = T +C = T +C +C =T + 2C
Basic 2  n4  4
recursive
algorithms = T + 3C
Recursion
8
trees method ..
Some
. n
formulas for
recurrences = T + kC
2k
n
We continue this process until we reach to = 1 and then
2k
n= 2k =⇒ k = log n. So we have T (n) = T (1) + kC
T (n) = C + kC ≈ k = log n
 Find asymptotic worst-case running time of the
BinarySearchRec.

Recursion Since the running time of the assignment

 nof midp is constant
Ali Alilooee then we have the recurrence T (n) = T + C . Then since
n n 2
Recursive
problems T =T + C we have
2 4
Substitution n n n
method
T (n) = T +C = T +C +C =T + 2C
Basic 2  n4  4
recursive
algorithms = T + 3C
Recursion
8
trees method ..
Some
. n
formulas for
recurrences = T + kC
2k
n
We continue this process until we reach to = 1 and then
2k
n= 2k =⇒ k = log n. So we have T (n) = T (1) + kC
T (n) = C + kC ≈ k = log n ⇒ T (n) ∈ Θ(log n).
 Merge Sort

Recursion Input: Array A of at least j elements.

Ali Alilooee Integers i and j .
Recursive
Result: A permutation of the i through j elements of A
problems such that A[i] ≤ A[i + 1] ≤ A[i + 2] ≤ · · · ≤ A[j].
Substitution
method
function MergeSort(A[], i, j)
Basic 1: if (i < j ) then
recursive
algorithms 2: midp ← b(i + j)/2c;
Recursion 3: MergeSort(A[], i, midp);
trees method
4: MergeSort (A[], midp + 1, j);
Some
formulas for 5: Merge (A[], i, midp, j);
recurrences
6: end if
 Merge Sort

Recursion Input: Array A of at least j elements.

Ali Alilooee Integers i and j .
Recursive
Result: A permutation of the i through j elements of A
problems such that A[i] ≤ A[i + 1] ≤ A[i + 2] ≤ · · · ≤ A[j].
Substitution
method
function MergeSort(A[], i, j)
Basic 1: if (i < j ) then
recursive
algorithms 2: midp ← b(i + j)/2c;
Recursion 3: MergeSort(A[], i, midp);
trees method
4: MergeSort (A[], midp + 1, j);
Some
formulas for 5: Merge (A[], i, midp, j);
recurrences
6: end if
As we will see soon the running time of the function Merge is
Θ(n). Then the recurrence of the MergeSort, so we have
n
T (n) = 2T + Cn
2
 Merge Sort

Recursion Input: Array A of at least j elements.

Ali Alilooee Integers i and j .
Recursive
Result: A permutation of the i through j elements of A
problems such that A[i] ≤ A[i + 1] ≤ A[i + 2] ≤ · · · ≤ A[j].
Substitution
method
function MergeSort(A[], i, j)
Basic 1: if (i < j ) then
recursive
algorithms 2: midp ← b(i + j)/2c;
Recursion 3: MergeSort(A[], i, midp);
trees method
4: MergeSort (A[], midp + 1, j);
Some
formulas for 5: Merge (A[], i, midp, j);
recurrences
6: end if
As we will see soon the running time of the function Merge is
Θ(n). Then the recurrence of the MergeSort, so we have
n
T (n) = 2T + Cn ∈ Θ(n log n)
2
 Copy Array

Recursion

Ali Alilooee

Recursive
problems Input: Array A of at least j elements.
Substitution Integers i and j .
method
Basic
Result: Array B containing A[i, i + 1, ..., j]
recursive
algorithms procedure Copy(A[], i, j, B[])
Recursion 1: p ← 1;
trees method
2: for k ← i to j do
Some
formulas for 3: B[p] ← A[k];
recurrences
4: p ← p + 1;
5: end for
 Merge

Recursion

Ali Alilooee procedure Merge(A[], first, midp, last)

1: Copy(A[], first, midp, L[]);
Recursive
problems 2: Copy(A[], midp + 1, last, R[]);
Substitution
method
3: i ← 1;
Basic 4: j ← 1;
recursive
algorithms
5: for k ← rst to last do
Recursion 6: if (L[i] < R[j]) then
trees method
7: A[k] ← L[i];
Some
formulas for 8: i ← i + 1;
recurrences
9: else
10: A[k] ← R[j];
11: j ← j + 1;
12: end if
13: end for
 Presentation Outline

Recursion

Ali Alilooee

Recursive 1 Recursive problems

problems
Substitution
method
2 Substitution method
Basic
recursive
algorithms
Recursion 3 Basic recursive algorithms
trees method
Some
formulas for
recurrences
4 Recursion trees method

5 Some formulas for recurrences

  
2n
n
T (n) = T +T + Cn ∈ Θ(n log n).
3 3
Recursion
Cn = Cn
Ali Alilooee
+
Recursive
problems 2Cn
Cn
3 + 3
= Cn
Substitution
method
Basic
+
recursive
algorithms Cn
+ 2Cn + 2Cn + 22 Cn =
32 32 32 32 Cn
Recursion
trees method +
Some
formulas for .. .. .. .. .. .. .. .. ··· ..
recurrences . . . . . . . . .
+
C +C + ··· + C +C = Cn
⇓ =
 Recursion

Ali Alilooee

Recursive
problems
Then we have T (n) = (k + 1)Cn when k is the level of the
Substitution tree.
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Recursion

Ali Alilooee

Recursive
problems
Then we have T (n) = (k + 1)Cn when k is the level of the
Substitution tree. So we just need to calculate k .
method
Basic
recursive
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Recursion

Ali Alilooee

Recursive
problems
Then we have T (n) = (k + 1)Cn when k is the level of the
Substitution tree. So we just need to calculate k .
method

2 3
 k  k
Basic
recursive n = 1 =⇒ n =
algorithms 3 2
Recursion
trees method
Some
formulas for
recurrences
 Recursion

Ali Alilooee

Recursive
problems
Then we have T (n) = (k + 1)Cn when k is the level of the
Substitution tree. So we just need to calculate k .
method

2 3
 k  k
Basic
recursive n = 1 =⇒ n = =⇒ k = log1.5 n ≈ log n
algorithms 3 2
Recursion
trees method
Some
formulas for
recurrences
 Recursion

Ali Alilooee

Recursive
problems
Then we have T (n) = (k + 1)Cn when k is the level of the
Substitution tree. So we just need to calculate k .
method

2 3
 k  k
Basic
recursive n = 1 =⇒ n = =⇒ k = log1.5 n ≈ log n
algorithms 3 2
Recursion
trees method
then we have
Some
formulas for
recurrences
T (n) = (log n + 1)Cn ≈ n log n =⇒ T (n) ∈ Θ(n log n).
 Presentation Outline

Recursion

Ali Alilooee

Recursive 1 Recursive problems

problems
Substitution
method
2 Substitution method
Basic
recursive
algorithms
Recursion 3 Basic recursive algorithms
trees method
Some
formulas for
recurrences
4 Recursion trees method

5 Some formulas for recurrences

 Divide and Conquer

Recursion

Ali Alilooee For the following recurrence for Divide and Conquer approach
Recursive
problems T (n) = aT (n/b) + f (n); for a ≥ 1 and b > 1
Substitution
method
we have the following special asymptotic complexities.
Basic
recursive
algorithms T (n) = T (n/2) + c; T (n) ∈ Θ(log2 n)
Recursion
trees method T (n) = T (n/3) + c; T (n) ∈ Θ(log2 n)
Some
formulas for T (n) = T (n/2) + cn; T (n) ∈ Θ(n)
recurrences
T (n) = T (n/3) + cn; T (n) ∈ Θ(n)
T (n) = 2T (n/2) + cn; T (n) ∈ Θ(n log2 n)
T (n) = 3T (n/3) + cn; T (n) ∈ Θ(n log2 n)
 More Divide and Conquer

Recursion

Ali Alilooee

Recursive
For the following recurrence for Divide and Conquer approach
problems
Substitution T (n) = aT (n/b) + f (n); for a ≥ 1 and b > 1
method
Basic
recursive we have the following special asymptotic complexities.
algorithms
Recursion
trees method
T (n) = 3T (n/2) + cn; T (n) ∈ Θ(nlog2 3 )
Some T (n) = 4T (n/2) + cn; T (n) ∈ Θ(nlog4 3 ) = Θ(n2 )
formulas for
recurrences T (n) = 2T (n/2) + cn2 ; T (n) ∈ Θ(n2 )
T (n) = 4T (n/2) + cn2 ; T (n) ∈ Θ(n2 log n)
 Asymmetric Recurrence Relations

Recursion We have the following special asymptotic complexities.

Ali Alilooee
T (n) = T (n/3) + T (2n/3) + cn; T (n) ∈ Θ(n log2 n)
Recursive
problems T (n) = T (n/4) + T (3n/4) + cn; T (n) ∈ Θ(n log2 n)
Substitution
method
T (n) = T (n/5) + T (4n/5) + cn; T (n) ∈ Θ(n log2 n)
Basic T (n) = T (2n/5) + T (3n/5) + cn; T (n) ∈ Θ(n log2 n)
recursive
algorithms T (n) = T (n/6) + T (2n/6) + T (3n/6) + cn; T (n) ∈ Θ(n log2 n)
Recursion
trees method
Some
formulas for
recurrences T (n) = T (n/4) + T (2n/4) + cn; T (n) ∈ Θ(n)
T (n) = T (n/5) + T (2n/5) + cn; T (n) ∈ Θ(n)
T (n) = T (n/5) + T (3n/5) + cn; T (n) ∈ Θ(n)
T (n) = T (n/6) + T (4n/6) + cn; T (n) ∈ Θ(n)
 Exponential Functions

Recursion

Ali Alilooee

Recursive
Assume f (n) ≥ 0 and T (1) > 0.
problems
Substitution T (n) = 2T (n − 1) + f (n); T (n) ∈ Ω(2n )
method
Basic T (n) = 3T (n − 1) + f (n); T (n) ∈ Ω(3n )
recursive
algorithms T (n) = 4T (n − 1) + f (n); T (n) ∈ Ω(4n )
Recursion
trees method
n
Some
formulas for
T (n) = T (n − 1) + T (n − 2) + f (n); T (n) ∈ Ω(2 2 )
recurrences n
T (n) = T (n − 1) + T (n − 2) + T (n − 3) + f (n); T (n) ∈ Ω(2 2 )
 Master Theorem

Recursion

Ali Alilooee Let a ≥ 1 and b > 1 be constants and let f (n) be a

Recursive
nonnegative function. Dene
problems
Θ(1)  if n = 1
(
Substitution
method T (n) = n
Basic aT + f (n) if n = b i
recursive b
algorithms
Recursion
trees method
Some
formulas for
recurrences
 Master Theorem

Recursion

Ali Alilooee Let a ≥ 1 and b > 1 be constants and let f (n) be a

Recursive
nonnegative function. Dene
problems
Θ(1)  if n = 1
(
Substitution
method T (n) = n
Basic aT + f (n) if n = b i
recursive b
algorithms
Recursion
trees method If f (n) ∈ O(nlogb a− ) for some constant  > 0 then
Some
formulas for
T (n) ∈ Θ(nlogb a ).
recurrences
 Master Theorem

Recursion

Ali Alilooee Let a ≥ 1 and b > 1 be constants and let f (n) be a

Recursive
nonnegative function. Dene
problems
Θ(1)  if n = 1
(
Substitution
method T (n) = n
Basic aT + f (n) if n = b i
recursive b
algorithms
Recursion
trees method If f (n) ∈ O(nlogb a− ) for some constant  > 0 then
Some
formulas for
T (n) ∈ Θ(nlogb a ).
recurrences
If f (n) ∈ Θ(nlogb a ) then T (n) ∈ Θ(nlogb a log n).
 Master Theorem

Recursion

Ali Alilooee Let a ≥ 1 and b > 1 be constants and let f (n) be a

Recursive
nonnegative function. Dene
problems
Θ(1)  if n = 1
(
Substitution
method T (n) = n
Basic aT + f (n) if n = b i
recursive b
algorithms
Recursion
trees method If f (n) ∈ O(nlogb a− ) for some constant  > 0 then
Some
formulas for
T (n) ∈ Θ(nlogb a ).
recurrences
If f (n) ∈ Θ(nlogb a ) then T (n) ∈ Θ(nlogb a log n).
If f (n) ∈ Ω(nlogb a+ ) for some constant  > 0 and if
af ( bn ) ≤ cf (n) for some constant c < 1 and all sucient
large n, then T (n) ∈ Θ(f (n)).