Runtime Analysis of Search Algorithm
Not what you're looking for?
Consider searching algorithms on the following array of data:
[22 21 9 4 16 2 10 14 20 31 26 19 17 28 8 13]
Suppose you want to implement a searching algorithm to see if the data set contains the number 19. Demonstrate how the search would go if you used:
A sequential search
A binary search
State the runtime for each of the searches, in this example, and for general data sets of size n. Address the issue of the order of the data in binary searching.
Suppose an algorithm that processes a data set of size 8 has a runtime of 72, and the same algorithm on a data set of size 20 has a runtime of 420. Using big-O notation, state the runtime for this algorithm for the general case of a data set of size n.
Suppose you develop an algorithm that processes the first element of an array (length of n), then processes the first 2 elements, then the first 3 elements, and so on, until the last iteration of a loop, when it processes all elements. Thus, if n = 4, the runtime would be 1 + 2 + 3 + 4 = 10.
Create a table that depicts the runtime for arrays of length 1 to 10. Would you expect the general runtime to be O(n), O(n2), O(n3), or some other function of n? Explain.
Purchase this Solution
Solution Summary
We analyze the runtime of a seqential search and binary search algorithm.
Solution Preview
A sequential search of the array for the number 19 would go through each element of the array starting with the first until the number 19 was found. The runtime for this algorithm is O(n), where n is the size of the array.
A binary search would involve first sorting the array, which can be done in time O(log n), and then ...
Purchase this Solution
Free BrainMass Quizzes
Basic Networking Questions
This quiz consists of some basic networking questions.
C++ Operators
This quiz tests a student's knowledge about C++ operators.
Excel Introductory Quiz
This quiz tests your knowledge of basics of MS-Excel.
Basic Computer Terms
We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.
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.