GATE Computer Science Engineering(CSE) 2027 Test: Asymptotic Worst Case

The recurrence tree for merge sort will have height Log(n). And O(n^2) work will be done at each level of the recurrence tree (Each level involves n comparisons and a comparison takes O(n) time in worst case). So time complexity of this Merge Sort will be [Tex]O (n^2 log n) [/Tex].

The recursion expression becomes: T(n) = T(n/4) + T(3n/4) + cn After solving the above recursion, we get  θ(nLogn).

For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot. If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced.

According to order of growth: h(n) < f(n) < g(n) (g(n) is asymptotically greater than f(n) and f(n) is asymptotically greater than h(n) ) We can easily see above order by taking logs of the given 3 functions

lognlogn < n < log(n!) (logs of the given f(n), g(n) and h(n)).

Note that log(n!) =

Above code is implementation of the Euclidean algorithm for finding Greatest Common Divisor (GCD).

Worst case complexities for the above sorting algorithms are as follows: Merge Sort — nLogn Bubble Sort — n^2 Quick Sort — n^2 Selection Sort — n^2

g(n) = f(n) and g(n) are of same asymptotic order and following statements are true. f(n) = O(g(n)) g(n) = O(f(n)). (a) and (b) are false because n! is of asymptotically higher order than.

(I) (n+m)^k = n^k + c1*n^(k-1) + ... k^m = θ(n^k)
(II) 2^(n+1) = 2*2^n = θ(2^n)

Let array be sorted in ascending order, if sum of first two elements is less than 1000 then there are  two elements with sum less than 1000 otherwise not. For array sorted in descending order we need to check last two elements. For an array data structure, number of operations are fixed in both the cases and not dependent on n, complexity is O(1)

The outer loop runs n/2 or θ times. The inner loop runs θ(Logn) times (Note that j is multiplied by 2 in every iteration). So the statement "k = k + n/2;" runs θ(nLogn) times. The statement increases value of k by n/2. So the value of k becomes n/2* θ(nLogn) which is θ(n^2Logn)

Time complexity of Heap Sort is θ(mLogm) for m input elements. For m = , the value of θ(m * Logm) will be which will be [ which is θ(Log n)

Time complexity of fun1() can be written as T(n) = T(n-1) + C which is O(n) Time complexity of fun2() can be written as T(n) = 2T(n-1) + C which is O(2^n)

Answer(B) The recursion expression becomes: T(n) = T(n/4) + T(3n/4) + cn After solving the above recursion, we get heta(nLogn).

For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot. If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced.

We can see it by taking few examples like n = 1, n = 3, etc.

For example, for n=5 we have the following (4) comparisons:

CEIL(log_2 n)+2 = CEIL(log_2 5) + 2 = CEIL(2.3) + 2 = 3 + 2 = 5

The variable j is initially 0 and value of j is sum of values of i. i is initialized as n and is reduced to half in each iteration. j = n/2 + n/4 + n/8 + .. + 1 = Θ(n) Note the semicolon after the for loop, so there is nothing in the body.

To find minimum and maximum element out of n numbers, we need to have at least (3n/2-2) comparisons.

The central element may always be an extreme element, therefore time complexity in worst case becomes O(n²)

Note that the function foo() is recursive. Space complexity is O(n) as there can be at most O(n) active functions (function call frames) at a time.