In questions 7-10 find the \"best\" big-O notation to describe the complexity of

Question

In questions 7-10 find the "best" big-O notation to describe the complexity of the algorithm. Choose your answers from the following: 1, log_2 n, n, nlog_2 n, n^2, n^3, ..., 2^n, n! The number of print statements in the following: i:= 1, j:= 1 while i lessthanorequalto n while j lessthanorequalto i print "hello"; j: = j + 1 i:= i + 1 In questions 7-10 find the "best" big-O notation to describe the complexity of the algorithm. Choose your answers from the following: 1, log_2n, n, n log_2 n, n^2, n^3, ..., 2^n, n! A binary search of n elements. A linear search to find the smallest number in a list of n numbers. The number of print statements in the following: i:= 1, j = 1 while i lessthanorequalto n while j lessthanorequalto i print "hello"; j:= j + 1 i:= i + 1 An algorithm that finds the average of n numbers by adding them and dividing by n.

Explanation / Answer

7:

Binary search in n element.

…

In binary search in sorted n numbers

Say arr = 1,2,3,….,n we need to search 'num'

We search if arr[mid]=num

If arr[mid]>num this indicate that num has to be present in left part of array

If arr[mid]<num this indicate that num has to be present in right part of array

So overall complexity is O(logn)

8:

Linear search to find smallest number in a list of n number

As we need to scan all the n elements atleast one so overall complexity is O(n)

9:

i=1 j=1

While i<n

While j<I

Print hello

j=j+1

i=i+1;

For I =1

Innter loops executed for 1

For i=2

Inner loop executed for 2

For I=3

Inner loop executed for 3

..

..

For i=n

Inner loop executed for n

So overall

1+2+…+n times inner loop executed .

So overall complex city = O(n^2)

10:

An algorithm that finds the average of n number by adding them and dividing by n

We need to scan all elements to add them all so overall complexity is O(n)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.