CMPS 3140 Complexity Review
| Example Algorithm | Explanation | |
| Pseudocode |
MERGE-SORT A[1 . . n]
1.If
n
= 1,
done.
2.Recursively sort
A[
1 . .
én/2ù
]
and
A[
én/2ù+1
. .
n
]
.
3.“Merge”
the
2
sorted lists.
|
White the pseudocode to "high-level" discribe the algorithm |
| Prove the Correctness |
Proof by induction:
1.Base case: if n = 1, the algorithm will return the
correct answer because
A[1..1]
is already sorted.
2.Inductive hypothesis: assume that the algorithm correctly
sorts
A[1.. én/2ù ] and A[én/2ù+1..n].
3.Step: if
A[1..
én/2ù
]
and
A[én/2ù+1..n]
are both correctly sorted, the whole array
A[1..
én/2ù
]
and
A[én/2ù+1..n]
is sorted after merging.
|
Mathematical proof: for each input it produces the expected output |
| Time Efficiency Analysis |
T(n)
=Q(1)
if
n
= 1; |
A measure of amount of time(how do you define "time"? ) for an algorithm to execute |
| Space Efficiency Analysis | ...... | ...... |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Two types of algorithm (Iterative vs Recursive)
Compute the Power of an integer: how can we compute bn with recursive algorithm? What's performance difference between following two algorithms?
| def
power(b, n): pow = 1 for i in range(n): pow = pow * b return pow |
def power(b, n): if n == 0: return 1 pow = power(b, n // 2) if n & 1: #odd return b * pow * pow return pow * pow #even |
How to formally calculate algorithm complexity
- Decide on a parameter indicating an input’s size.
- Identify the algorithm’s basic operation.
- Check whether the number of times the basic op. is executed may vary on different inputs of the same size. (If it may, the worst, average, and best cases must be investigated separately.)
- The total number of times the basic op. is executed.
- Find out solution’s order of growth
- Analyzing the complexity of an algorithm (Iterative)
- Analysis of Recursive Algorithms
|
|
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
How to find out the order of growth
- O: Big-Oh
Ω: Big-Omega
Θ: Theta
o: Small-oh
ω: Small-omega - Proof by definition
- Using limits to compare orders of growth