State runtime for algorithm for the general case of data set

Question

1) 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.

 

(a) Demonstrate (with diagrams like the ones I show in the live chats and in the Phase 5 PowerPoint Guide) how the search would go if you used:

 

•  
  • A sequential search
  • A binary search

 

(b) State the runtime for each of the searches, in this example, and for general data sets of size n. (and how you reached this run time)

 

(c) Address the issue of the order of the data in binary searching.

 

2) 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. Show your work.

 

3) 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 n. Would you expect the general runtime to be O(n), O(n²), O(n³), or some other function of n? Explain.