Maths - Algorithm Analysis Problem

Question # 00013742 Posted By: expert-mustang Updated on: 04/28/2014 12:56 AM Due on: 04/28/2014
Subject Mathematics Topic Algorithms Tutorials:
Question
Dot Image


Algorithm Analysis


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. The same algorithm has a runtime of 110 when applied to a data set of size 10; and when applied to a data set of size 20, it 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.

Dot Image
Tutorials for this Question
  1. Tutorial # 00013301 Posted By: expert-mustang Posted on: 04/28/2014 01:00 AM
    Puchased By: 3
    Tutorial Preview
    set as: 72 = 82 + 8 110 = 102 + 10 240 = 202 + 20 The runtime is then related to the size ...
    Attachments
    Maths_-_Algorithm_Analysis_Problem_Solution_(Detailed).docx (48.08 KB)
    Recent Feedback
    Rated By Feedback Comments Rated On
    ho...g467 Rating Easy tutorial order-placing 12/05/2016

Great! We have found the solution of this question!

Whatsapp Lisa