MCQ-Complexity Analysis Doubts

#1

Can anyone explain questions 8, 10, 11,12 and 13(of which the answer I think is not correct)

#2

Hello @Mp18,

Ques 8:
The best approach of finding square root is by using binary search.
The time complexity of binary search is log(n)

Ques 10:
Observe the following graphs:

jIi9L.jpg491×609 19.9 KB

Once, both the curves intersect they never meet again.
As you can see, the value of O{n^3} >= O(2^n), for n>=10

Ques 11:
There is an optimized version of bubble sort:
Check if there happened any swapping operation in the inner loop (pass execution loop) or not. If there is no swapping in any pass, it means the array is now fully sorted, hence no need to continue, stop the sorting operation.

  1. we know that it the simplest
  2. Best case of bubble is O(1) for optimized version and O(n) for normal, while it is O(n^2) for insert.

Ques 13:
You can use master’s theorem:
T(n) = aT(n/b) + f(n) where a >= 1 and b > 1
There are following three cases:

  1. If f(n) = Θ(n^c) where c < Logb(a) then T(n) = Θ(nLogba)

  2. If f(n) = Θ(n^c) where c = Logb(a) then T(n) = Θ((n^c)*(Log n))

3.If f(n) = Θ(n^c) where c > Logb(a) then T(n) = Θ(f(n))

using case 2:
Aswer is Θ(nlogn)

Hope, this would help.
Give a like, if you are satisfied.

#3

For question 10, what does 2^(O(n)) mean?
And isn’t O(n^3) greater when n<=10?
Can you also explain Q12?

#4

Ques 10:
O(2^n) is same as 2^O(n)

Ques 12:
If we consider the binary selection algorithm, then each time we reduce the array by half.
answer is n/2

Hope, this would help.
Give a like, if you are satisfied.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.