Question is from algorithams analysis & design course.

4. Let T[1], T[2], ..., T[n], be n distinct (i.e. no repetitions) sorted integers (possibly negative). You want to nd out if there is an index k such that T[k] = k.

For example, if n = 5, and the array T is T[1] = 2,T[2] = 0,T[3] = 1,T[4] = 4,T[5] = 32, the answer should be YES because T[4] = 4. If n = 5, and the array T is T[1] = 7,T[2] = 4,T[3] = 7,T[4] = 8,T[5] = 13, the answer should be NO.

You have to nd an ecient algorithm to solve this problem; in the worst case, your algorithm should take time less than O(n). However, if you cant nd an algorithm faster than O(n), at least present your O(n) time algorithm - i will get partial credit for this.

Hint: Remember that the integers in the array have to be distinct, and use an approach similar to binary search.

(a) Give a very short and clear description in English of the basic idea behind your algorithm.

(b) Give the pseudocode.

(c) Trace the execution of your algorithms on the two examples given above.

(d) Do a worst case time analysis (use big O notation) of your algorithm.