TCS Ninja Programming Logic Time Complexity Quiz-1

The first loop is O(N) and the second loop is O(M). Since we don’t know which is bigger, we say this is O(N + M). This can also be written as O(max(N, M)).
Since there is no additional space being utilized, the space complexity is constant O(1).

We have to find the smallest x such that N / 2^x N
x = log(N)

In the asymptotic analysis, we consider the growth of algorithm in terms of input size. An algorithm X is said to be asymptotically better than Y if X takes smaller time than y for all input sizes n larger than a value n0 where n0 > 0.

If you notice, j keeps doubling till it is less than or equal to n. A number of times, we can double a number until it is less than n would be log(n).
Let’s take the examples here.
for n = 16, j = 2, 4, 8, 16
for n = 32, j = 2, 4, 8, 16, 32
So, j would run for O(log n) steps.
i runs for n/2 steps.
So, total steps = O(n/ 2 * log (n)) = O(n*logn)

The above code runs total no of times
= N + (N – 1) + (N – 2) + … 1 + 0
= N * (N + 1) / 2
= 1/2 * N^2 + 1/2 * N
O(N^2) times.

The null case does not exist in complexity theory.

This happens when the pivot is the smallest (or the largest) element. Then one of the partitions is empty, and we repeat recursively the procedure for N-1 elements.

The worst-case complexity of quicksort is O(n²).

The worst case complexity for merge sort is O(nlogn)

In the worst case, the nth comparison is required to insert the nth element into the correct position.