Mphasis Complexity Theory Quiz-1

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

The time complexity of MergeSort is O(n*Log n) in all the 3 cases (worst, average and best) as the mergesort always divides the array into two halves and takes linear time to merge two halves.

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

Asymptotic Notation is used to describe the running time of an algorithm - how much time an algorithm takes with a given input, n. There are three different notations: big O, big Theta (Θ), and big Omega (Ω). big name doesn't represents any notation.

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.

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.

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).

In the given code we set i at N, and decrement it by 1/2 in each iteration so, The time complexity will be O(logN).

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 i.e log216 is 4
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

Time Complexity :: O(N^2) times.