Test: Algorithm Analysis & Asymptotic Notation- 1 - Computer Science Engineering (CSE) MCQ

Sorting is useful for making search easier and efficient and in report generation but not minimize the space needed.

In the worst case it has to check all the 2ⁿ possible input combinations, which is exponential.

Let there be ‘n' items to be searched, After the first search the list is divided into two, each of length n/2 . After the next search, 2 lists, each of length n/4  and so on. This successive division has to stop when the length of list becomes 1. Let it happen after k steps.
After the k steps,

Hence the order is log(n).

Each comparison will append one item to the existing merge list. In the worst case one needs m + n -1 comparisons which is of order m+ n.

In the best case quick sort algorithm makes O(nlog (n)) comparisons.
So 1000 x log (1000) = 9000 comparisons, which takes 100 sec.
To sort 100 names a minimum of 100 (log 100) = 600 comparisons are-needed.

For sorting 200 names bubble sort makes   comparisons. The time needed  for 1 comparison is 200 sec (approximately). In 800 sec it can make 80,000 comparisons. We have to find n, such that 

Solving, n is approximately 400.

Unrestricted use of goto statement is harmful because it makes more difficult to verify programs i.e. use of goto can results in unstructured code and there can be blocks with multiple entry and exit which can cause difficulty which debugging of program.

Since, with every iteration of Binary Search, data set to be searched is divided into half of the original/earlier dataset. Also, same constant time is lapsed during each iteration. So, recurrence relation for Binary Search would be:

In this question total possibility is four but only two possibility will give solution and other two possibilities will not give solutions. 
g(n) = O (f(n))
In case of 0 ≤ n < 100 & & 0 ≤n< 10,000 
(it is also not possible)
in case of otherwise From the above two equations the conclusion is O(f (n)) is same as O(g(m)) and g(n) and f(n) will be O(n²).