Recurrent Algorithms
Divide-and-conquer principle:
to divide a large problem into smaller ones and recursively solve each subproblem, then
to combine solutions of the subproblems to solve the original problem
Running time: by a recurrence relation combining the size and number of the subproblems
and the cost of dividing the problem into the subproblems
Lecture 5
“Telescoping” a Recurrence
Recurrence relation and its base condition (i.e., the difference equation and initial
condition):
T(n) = 2⋅T(n−1) + 1; T(1) = 1
Closed (explicit) form for T(n) by “telescoping”:
Lecture 5
“Telescoping” ≡ Substitution
Lecture 5
Basic Recurrence: 1
Closed (explicit) form by “telescoping”:
Lecture 5
1: Explicit Expression for T(n)
Lecture 5
Guessing to Solve a Recurrence
Infer (guess) a hypothetic solution T(n); n ≥ 0 from a sequence of numbers T(0), T(1), T(2), …,
obtained from the recurrence relation
Prove T(n) by math induction:
Base condition: T holds for n = nbase ,e.g. T(0) or T(1)
Induction hypothesis to verify: for every n > nbase, if T holds for n − 1,
then T holds for n
Strong induction: if T holds for nbase, …, n - 1, then…
Lecture 5
Explicit Expression for T(n)
T(1) = 1; T(2) = 1 + 2 = 3; T(3) = 3 + 3 = 6;
T(4) = 6 + 4 = 10 ⇒ Hypothesis:
Base condition holds: T(1) = 1∙2 / 2 = 1
If the hypothetic closed-form relationship T(n) holds for n − 1 then it holds also for n:
Thus, the expression for T(n) holds for all n > 1
Lecture 5
Basic Recurrence: 2
Repeated halving principle: halve the input in one step:
“Telescoping” (for n = 2m):
Lecture 5
2: Explicit Expression for T(n)
Lecture 5
Basic Recurrence: 3
Scan and halve the input:
“Telescoping” (for n = 2m):
Lecture 5
3: Explicit Expression for T(n)
Lecture 5
Basic Recurrence: 4
“Divide-and-conquer” prototype:
“Telescoping”:
For
Lecture 5
4: Explicit Expression for T(n)
Lecture 5
General “Divide-and-Conquer”
Theorem: The recurrence
with integer constants a≥1 and b≥2 and positive
constants c and k has the solution:
Proof by telescoping:
Lecture 5
General “Divide-and-Conquer”
Telescoping:
Lecture 5
Recursion Example
long factorial( int n )
{ In terms of big-Oh:
if( n <= 1 ) t(1) = 1
return 1; t(n) = 1 + t(n-1) = 1 + 1 + t(n-2)
else = ... k + t(n-k)
return n*factorial(n- 1); Choose k = n-1
}
t(n) = n-1 + t(1) = n-1 + 1 = O(n)
Consider the following time complexity:
t(0) = 1
t(n) = 1 + 2t(n-1) = 1 + 2(1 + 2t(n-2)) = 1 + 2 + 4t(n-2)
= 1 + 2 + 4(1 + 2t(n-3)) = 1 + 2 + 4 + 8t(n-3)
= 1 + 2 + ... + 2k-1 + 2kt(n-k)
Choose k = n
t(n) = 1 + 2 + ... 2n-1 + 2n = 2n+1 - 1
Another Approach (Recursive Tree Method)
• T(n) = 2T(n/2) + O(n) , T(1) = O(1)
T(n) = T(n/2) + T(n/2) + cn = cn = cn
T(n/2) T(n/2) c(n/2) c(n/2)
height
T(n/2k) = T(1) where k= height,
K= lgn T(n/4) T(n/4) T(n/4) T(n/4)
O(n) = O(height * number of leaves)
= O(k*n)=O(nlgn) T(1) T(1)
No of leaves
Another Example
•
Capabilities and Limitations
Rough complexity analysis cannot result immediately in an efficient practical program but
it helps in predicting of empirical running time of the program
“Big-Oh” analysis is unsuitable for small input and hides the constants c and n0 crucial for
a practical task
“Big-Oh” analysis is unsuitable if costs of access to input data items vary and if there is
lack of sufficient memory
But complexity analysis provides ideas how to develop new efficient methods
Lecture 5