Description

a. () = (()), (()), Ω(())
b. () = (()), (()), Ω(())
c. () = Ω(())
d. () = Ω(())
e. () = (())

a. This algorithm finds the minimum integer in an array of integers.
b. () = 2()
2
Base Case: Assume = 2 and n=2 and k=1
(2) = 2 which means the base case is true.
Hypothesis: Assume (2) = 2
Induction: (2−1), n=3, k=2
(23−1) = 2 (22) = 4
2
Induction is proved true.

c.
Level Level number Total # of recursive executions at this level Input size to each recursive execution Work done by each recursive execution, excluding the recursive calls Total work done by the algorithm at this level
Root 0 2

2 c c
One level below root 1 4

4 c 2c
Two level below root 2 8

8 c 4c
The level just above the base case level log(n-1) n 1 c 11

2
Base case level log(n) 0 0 c n(c)
d. The complexity of the algorithm is T(1) = c, T(n>1) = 2T(n/2) + n.

Level Level number Total # of recursive executions at this level Input size to each recursive execution Work done by each recursive execution, excluding the recursive calls Total work done by the algorithm at this level
Root 0 n(c) n(c) n(c)
One level below root 1

8

Two level below root 2 72
(c)
The level just above the base case level log8 -1
Base case level log8 7 log8 1 c ∗ 7 log8

Statement of what you have to prove:
() = 3 () + 5; (1) = 5
3
Base Case proof: T(1) = 5 so T(1) = O(n) Inductive Hypotheses:
T(k) = O(k) for some fixed c, and ∀ > , so T(k) < c(k) Inductive Step:
( + 1) = ( + 1)
( + 1) < 3 ∗ ∗ + 5
3
( + 1) < ∗ + 5
( + 1) < ( + 1) + 5 − Value of c:
If c = 5, ( + 1) < ( + 1)
∴ Passed

5. Let () = 2 + , () = 2, () = 2 − , () = 2.
Therefore, () = (()), () = (()
() − () = 2 − 2 = 0 = (1)
(() − ()) = (2 + − (2 − )) = ()
∴ () − () ≠ (() − ())

6.

Total work:
Level 1 = n
Level 2 = =
2
Level 3 = + 2 ( + + + ) =
4 8 16 16 8 16 32 32 16 32 64 64
3. The shortest branch will be the depth at the shallowest point.
4 = 1
8
= log8 = log23 = log2
Depth = log2
4. The longest branch will be the depth at the deepest point.

log2 = log
log2 2 = log
= log
Depth = log
5.
() = () − 1

() = Ω() − 1
∴ T(n) = O(n)
7. Statement of what you have to prove:
() = () + () + () + () + ; (1) =
2 4 8 8
Base Case proof:
(1) =
Inductive Hypotheses:
T(k) = O(k) for some fixed c, and ∀ > , so T(k) < c(k) Inductive Step:
( + 1) = ( +1) + ( +1) + ( +1) + ( +1)
2 4 8 8

8. a. () = 2 (99) + 100
100
() = 2( 100 ) + 100
() 99
= 2, = 100/99
log1002
99 > () = 100
log1002
Time complexity = ( 99 )[
b. () = 16 () + 3 log
2
= 16, = 2
log216 > () = 3 log
Time Complexity = (4)

c. () = 16 () + 2
4
= 16, = 4
log416 = () = 2
Time complexity = (2 log )
9. Backwards Substitution
1. () = 2( − 1) + 1
(1) = 2(1 − 1) + 1 = 3
(2) = 2(2 − 1) + 1 = 7
(3) = 2(3 − 1) + 1 = 15
2. () = 2( − 1) + 1 = 2(2( − 2) + 1) + 1
() = 4( − 2) + (1 + 2)
() = 4(2( − 3) + (1 + 2))
() = 8( − 3) + (1 + 2 + 4)
() = 2(−1)(1) + (1 + 2 + 4 … + 2−2)
() = 2 + 2 − 1
() = 2+1 − 1
3. Base Case: = 0, (0) = 20+1 − 1 = 1
Assume: () = 2+1 − 1
So: ( + 1) = 2+2 − 1
( + 1) = 2() + 1 => 2(2+1 − 1) + 1 = 2+2 − 1
4. Complexity order = 2
Forwards Solution
1. () = 2( − 1) + 1
(1) = 2(1 − 1) + 1 = 3
(2) = 2(2 − 1) + 1 = 7
(3) = 2(3 − 1) + 1 = 15
2. = +−11−1 = 22++11−−11−−11
3. See part 1.
4. T(n) = 2+1 − 1 = (2)

10. () = ( − 1) + , (1) = 1
2

( − ) = ( − ) + ( − + 1) + ( − + 2) + ⋯ +)/2
So,
() = (+1)
8

11. Let = 2
(2) = () = 2( − 1) + 2
(2) = 2(2( − 2) + − 1)2−1) + 2
(2) = 4(2( − 3) + ( − 2)2−2) + ( − 1)2 + 2
(2) = 8( − 3) + ( − 2)2 + ( − 1)2 + 2

() = 2(0) + ( + 1)2−1

() = (1) + ((log2()(1+log2())) = (2)
2

12. This is pointless because this means the algorithm can having a maximum run-time of O(n^2), but this is true for every algorithm. This algorithm could also have a run-time of anything slower than O(n^2).