CS502 Assignment 1 Solution Fall 2017
Question # 1:
Let us use the same logic which the book uses i.e. any array access is considered a single operation. Also, consider that the array A has n elements.
i ← 1 .. 1 initialization takes constant time
while (A[i] ≠ key) and (i ≤ length[A]) .. 1 array access taking constant time
i ← i + 1 .. 1 operation taking constant time
if ( i ≤ length[A]) return true .. 1 operation of comparison
else return false
Best case happens when the key is found in first iteration i.e. at first position. In that case, the loop executes a single time only giving:
Best case big-Oh O(1) i.e. only one iteration
Worst case happens when the key is not found at all. This means that the loop executes for n times.
Worst case big-Oh O(n) i.e. n iterations
Average case happens when the key is not found in the center of the array i.e. n/2 iteration.
Average case big-Oh O(n/2) i.e. n/2 iterations
Question # 2:
Yellow boxes are always the pivots. Red is the position of the swap. The final row in each recursion always shows where the pivot comes to after the partition algorithm has executed.
algo assignment, algorithm assignment, assignment solution cs502, cs502, cs502 assignment, cs502 assignment 1, cs502 assignment 1 solution, cs502 assignment 1 solution 2017, cs502 assignment 2017, cs502 assignment solution 2017, algorithm assignment solution, fundamentals of algorithms assignment 1 solution.