Analysis and Design of Algorithms - Assignment 2
Group 18
Donald Onyino Simwa - P15/2101/2021
Sherry Kisilu - P15/1915/2022
Question 1:
1. Write a recursive algorithm to solve the problem. Assume that there exists a function
“max(a, b)” that returns the maximum of two integers a and b
findMax(A, n)
// Input: A an array of numbers, n the length of the array
// Output: The max number from the array
if n == 1:
return A[0]
return max(A[n -1], findMax(A, n-1))
2. Proof of correctness
Mathematical Induction
Base Case:
When n = 1, the array has only one element, this element will be the
maximum, so the base case holds
Inductive Hypothesis:
If the algorithm works correctly for all arrays of size k, where k >= 1. We assume for
an array A of size k the algorithm returns the max element
findMax(A, k) = max(A[0], A[1], …, A[k-1])
Inductive Step:
Let A be an array of size k + 1
The algorithm divides the problem as follows:
findMax(A, k + 1) = max(A[k], findMax(A, k))
substituting findMax(A, k)
findMax(A, k +1) = max(A[k], max(A[0], A[1],...,A[k-1])
therefore
findMax(A, k + 1) = max(A[0], A[1], …, A[k])
3. Derive the recurrence relation and solve it
n = 1, A[0] constant time = O(1)
n > 1, findMax(A,n) = max(A[n-1], findMax(A, n- 1)), max operation takes O(1)
T(n) = T (n - 1) + O(1)
Solving:
c is the constant cost of the max operation
T(n) = T (n-1) + c
Expanding the recurrence:
T(n) = T(n -1) + c
T(n - 1) = T(n - 2) + c
T(n - 2) = T (n - 3) + c
.
.
.
T(2) = T(1) + c( n - 1)
T(1) = O(1)
T(n) = O(1) + (n-1)c
T(n) = cn + O(1)
T(n) = O(n)
Question 2
Expanding the recurrence
T(n) = 2T(n/2) + n
Substitute T(n/2)
T(n) = 2(2T(n/4) + n/2) + n
Simplifying:
T(n) = 4T(n/4) + 2(n/2) + n
T(n) = 4T(n/4) + n + n
Expanding T(n/4):
T(n) = 4 (2T(n/8) + n/4) + 2n
T(n) = 8T(n/8) + 4(n/4) + 2n
T(n) = 8T(n/8) + n + n + n
General Pattern:
After k steps:
T(n) = 2^kT(n/2^k)+kn
Stopping the recurrence:
Stops when n/2^k = 1 or n = 2^k
K = logn
T(n) = n x 0 + (logn)n
T(n) = nlogn
Question 3
Using a recursive tree, solve the recurrence equation T(n) = 3T(n/4) + cn^
cn^2
c(n/ c(n/ c(n/
c(n/ c(n/ c(n/ c(n/
c(n/ c(n/
c(n/ c(n/
c(n/
General Pattern - Cost at level k - 3^k x c(n/4^k)^2
log4 n
∑ ( 16 )
k
2 3
Total Cost = c ⋅n
k=0
This is a geometric series with ratio = 3/16 which is less than 1. As n grows larget the
geometric series converges to a constant
The dominant term is c x n^2
So the overall complexity is:
T(n) = O(n^2)
Question 4
Give the Θ bounds for the recurrence equation
a = 4,
b=2
f(n) = n^2
p=log b a=2
f(n) = n^2 matches n^p
For this case
p 2
f (n)=Θ(n log n)=Θ(n log n)
2
T (n)=Θ(n logn)
