Share
Explore BrainMass

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)?

Solution Preview

This solution has three parts.

(a) Suppose you know what k is. Give an algorithm to find the largest number in A.

Since the array was sorted to start with then we know that if it was not shifted then the last element in the list is the largest element. However, since it is circular shifted the last element has been moved. If the array was shifted by 1 element then the largest element would have moved to the front of the list. If the array was shifted by 2 elements then the largest would be at the second location. So we know that if the array is ...

Solution Summary

This solutions explains two algorithms for manipulating values in a list and explains the algorithmic complexity of each algorithm.

$2.19