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

T(n) = 1 = n

Best case happens when the key is found on 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

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

First recursion with k = 19
933 / 782 / 116 / 276 / 904 / 353 / 416 / 157 / 277 / 583 / 525 / 208 / 269 / 98 / 181 / 859 / 573 / 225 / 526 / 627 / 631 / 590 / 257 / 402 / 335
116 / 782 / 933 / 276 / 904 / 353 / 416 / 157 / 277 / 583 / 525 / 208 / 269 / 98 / 181 / 859 / 573 / 225 / 526 / 627 / 631 / 590 / 257 / 402 / 335
116 / 276 / 933 / 782 / 904 / 353 / 416 / 157 / 277 / 583 / 525 / 208 / 269 / 98 / 181 / 859 / 573 / 225 / 526 / 627 / 631 / 590 / 257 / 402 / 335
116 / 276 / 157 / 782 / 904 / 353 / 416 / 933 / 277 / 583 / 525 / 208 / 269 / 98 / 181 / 859 / 573 / 225 / 526 / 627 / 631 / 590 / 257 / 402 / 335
116 / 276 / 157 / 277 / 904 / 353 / 416 / 933 / 782 / 583 / 525 / 208 / 269 / 98 / 181 / 859 / 573 / 225 / 526 / 627 / 631 / 590 / 257 / 402 / 335
116 / 276 / 157 / 277 / 208 / 353 / 416 / 933 / 782 / 583 / 525 / 904 / 269 / 98 / 181 / 859 / 573 / 225 / 526 / 627 / 631 / 590 / 257 / 402 / 335
116 / 276 / 157 / 277 / 208 / 269 / 416 / 933 / 782 / 583 / 525 / 904 / 353 / 98 / 181 / 859 / 573 / 225 / 526 / 627 / 631 / 590 / 257 / 402 / 335
116 / 276 / 157 / 277 / 208 / 269 / 98 / 933 / 782 / 583 / 525 / 904 / 353 / 416 / 181 / 859 / 573 / 225 / 526 / 627 / 631 / 590 / 257 / 402 / 335
116 / 276 / 157 / 277 / 208 / 269 / 98 / 181 / 782 / 583 / 525 / 904 / 353 / 416 / 933 / 859 / 573 / 225 / 526 / 627 / 631 / 590 / 257 / 402 / 335
116 / 276 / 157 / 277 / 208 / 269 / 98 / 181 / 225 / 583 / 525 / 904 / 353 / 416 / 933 / 859 / 573 / 782 / 526 / 627 / 631 / 590 / 257 / 402 / 335
116 / 276 / 157 / 277 / 208 / 269 / 98 / 181 / 225 / 257 / 525 / 904 / 353 / 416 / 933 / 859 / 573 / 782 / 526 / 627 / 631 / 590 / 583 / 402 / 335
116 / 276 / 157 / 277 / 208 / 269 / 98 / 181 / 225 / 257 / 335 / 904 / 353 / 416 / 933 / 859 / 573 / 782 / 526 / 627 / 631 / 590 / 583 / 402 / 525
Rank_x = 11
So we take the right portion only
Now, k = 19-11= 8
Second recursion with k = 8
904 / 353 / 416 / 933 / 859 / 573 / 782 / 526 / 627 / 631 / 590 / 583 / 402 / 525
353 / 904 / 416 / 933 / 859 / 573 / 782 / 526 / 627 / 631 / 590 / 583 / 402 / 525
353 / 416 / 904 / 933 / 859 / 573 / 782 / 526 / 627 / 631 / 590 / 583 / 402 / 525
353 / 416 / 402 / 933 / 859 / 573 / 782 / 526 / 627 / 631 / 590 / 583 / 904 / 525
353 / 416 / 402 / 525 / 859 / 573 / 782 / 526 / 627 / 631 / 590 / 583 / 904 / 933
Rank_x = 4
So we take the right portion only
Now, k = 8-4 = 4
Third recursion with k = 4
859 / 573 / 782 / 526 / 627 / 631 / 590 / 583 / 904 / 933
Rank_x=10
So we take the left portion only
Now, k = 4
Fourth recursion with k = 4
859 / 573 / 782 / 526 / 627 / 631 / 590 / 583 / 904
Rank_x=9
So we take the left portion only
Now, k =4
Fifth recursion with k = 4
859 / 573 / 782 / 526 / 627 / 631 / 590 / 583
573 / 859 / 782 / 526 / 627 / 631 / 590 / 583
573 / 526 / 782 / 859 / 627 / 631 / 590 / 583
573 / 526 / 583 / 859 / 627 / 631 / 590 / 782
Rank_x = 3
So we take the right portion only
Now, k = 4-3=1
Sixth recursion with k = 1
859 / 627 / 631 / 590 / 782
627 / 859 / 631 / 590 / 782
627 / 631 / 859 / 590 / 782
627 / 631 / 590 / 859 / 782
627 / 631 / 590 / 782 / 859
Rank_x=4
So we take the left portion only
Now, k=1
Seventh recursion with k = 1
627 / 631 / 590
590 / 631 / 627
Rank_x=1
This is what we are looking for
So, the answer is 590