Explore BrainMass
Share

Analyzing algorithm complexity

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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

© BrainMass Inc. brainmass.com October 25, 2018, 1:49 am ad1c9bdddf
https://brainmass.com/computer-science/searching/analyzing-algorithm-complexity-276239

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
See Also This Related BrainMass Solution

Design and Analysis of Algorithms..

Consider a set G consisting of m integers.

a) Design an algorithm that finds and gives as output the k smallest numbers of the whole G sorted in ascending order and has time complexity O(m*lg(m)) and spatial complexity O(m).

Note: lg denote the logarithm base 2.

b) Design an algorithm that solves the above problem using a mandatory heap and has time complexity O(m + k*lg(m)) and space complexity O(m).

In response give either pseudocode or the description of the steps of the algorithm and justify the complexities.

View Full Posting Details