Analyzing algorithm complexity
Not what you're looking for?
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)?
Purchase this Solution
Solution Summary
This solutions explains two algorithms for manipulating values in a list and explains the algorithmic complexity of each algorithm.
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 ...
Purchase this Solution
Free BrainMass Quizzes
Javscript Basics
Quiz on basics of javascript programming language.
Inserting and deleting in a linked list
This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.
Basic Networking Questions
This quiz consists of some basic networking questions.
Java loops
This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.
Word 2010: Table of Contents
Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.