Question

List appropriate Worst Case Big O Notation under the different algorithms or data structure operations. 10 Points Please use black, blue, or dark green font color O(1) O(n) O(n ^ 2) O(log n) A. Directly Accessing value in a 2-dimensional by [row][column] B. Selection Sort then Binary Search on a 1,000,000 element array C. Binary Search D. Highest element algorithm for 10,000 element array. E. Traversal of 6 character string

Answer 1

Answer:

A. Bubble sort worst case complexity is O(n2). As nested for loop on two variables is used where outer loop runs from 0 to length of array and inner loop runs from 0 to number of elements not in place.

B. Directly Accessing value in a 2-dimensional by [row][column] is O(1). As row and column is defined directly access can be made.

C. Linear Search of a 100 element array is O(n). one loop from 1 to length of array will run.

D. Accessing middle element in an array by index is O(1). middle index can be computed and accessed directly.

mid = firstIndex+ (lastIndex-firstIndex)/2

E. Traversal of 20 character string O(length of string)=O(n) where n is length of string.