1 Given an array of numbers sorted from lowest to highest wh

1.)

Given an array of numbers sorted from lowest to highest, what would the (closest) runtime be for the best algorithm to find the largest number in the array?( Select all that apply from below)

2.)

3.)

What is the best asymptotic bound for this algorithm?

4.)

What is the best asymptotic bound for this algorithm?

Solution

1.
It will be O(1), theta(1), omega(1).
Because, since the array is sorted from lowest to highest we can directly return the last element of the array without having to traverse the array.

2.
f(n) = O(n^2), theta(n^2), omega(n^2) is the strongest fit. Anything more than that will also be a coorrect answer.
Like: O(n^3).

3.
The assymptotic bound is O(n^2) because the outer loop is running n times, and for each time the outer loop runs, the inner loop is running n times. So the complexity = O(n * n) = O(n^2)

4.
The assymptotic bound is O(n^3) because the first loop is running n times, and for each time the first loop runs, the second loop is running n times. , and for each time the second loop runs, the third loop is running n times. So the complexity = O(n * n * n) = O(n^3)