1) Write out the algorithm (pseudocode) to find K in the ordered array by the method that compares K to every fourth entry until K itself or an entry larger than K is found, and then, in the latter case, searches for K among the preceding three. How many comparisons does your algorithm do in the worst case?

2) Answer questions (a) and (b) below:

(a) How many times exactly is the code block below executed?

For (i = 1, n)

{

For (j = 1, i)

{

For (k = 1, j)

{

code block

}

}

}

Hint: You have to start with n=1, then make assumption what you make expect for any given n = N, and check if the formula you found works for n =N+1. This is what we call prove by induction.

(b) What is the theta value of this code segment?