Question:
Analyzing algorithm complexity
Suppose you are given an array A of n sorted numbers that has been circularly shifted k positions to the right. For example, {35, 42, 5, 15, 27, 29} is a sorted array that has been circularly shifted k = 2 positions, while {27, 29, 35, 42, 5, 15} has been shifted k = 4 positions.
(a) Suppose you know what k is. Give an algorithm to find the largest number in A.
(b) Suppose you do not know what k is. Give an algorithm to find the largest number in A.
(c) What is the time complexity of your algorithms in (a) and (b)?