# CS502 Assignment 1 Solution Fall 2017

## 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.

Search(A, Key)

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.