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

AVL tree is a balanced tree.
AVL tree's time complexity of searching = θ(logn) 
But a binary search tree, may be skewed tree, so in worst case BST searching time = θ(n)

Radix sort time complexity = O(wn)
for n keys of word size= w 
=>w = log(n^k) 
O(wn)=O(klogn.n) 
=> kO(nlogn)

The term O(1) states that the space required by the insertion sort is constant i.e., space required doesn't depend on input.

Following is the initial recursion tree for the given recurrence relation.

If we further break down the expression T(n/4) and T(n/2), we get following recursion tree.

Breaking down further gives us following

To know the value of T(n), we need to calculate sum of tree nodes level by level. If we sum the above tree level by level, we get the following series T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + .... The above series is geometrical progression with ratio 5/16 To get an upper bound, we can sum the above series for infinite terms. We get the sum as (n^2) / (1 - 5/16) which is O(n^2)

The given solution can be solved using Master Method. It falls in Case 1.

Following is the recurrence for given implementation of subset sum problem T(n) = 2T(n-1) + C1 T(0) = C1 Where C1 and C2 are some machine specific constants. The solution of recurrence is O(2^n) We can see it with the help of recurrence tree method

If we sum the above tree level by level, we get the following series T(n) = C1 + 2C1 + 4C1 + 8C1 + ...
The above series is Geometrical progression and there will be n terms in it.
So T(n) = O(2^n)

This question can be solved by first change of variable and then Master Method.

Above expression is a binary tree traversal recursion whose time complexity is θ(m). You can also prove using Master theorem.

S(m) = θ (m)
= θ (log n)

/* since n = 2^m */

Now, let us go back to the original recursive function T(n)

T(n) = T(2^m) = s(m)

=  θ (log n)

This can also be solved using Master Theorem for solving recurrences. The given expression lies in Case 3 of the theorem.

Recursive relation for the DoSomething() is

T(n) = T(√n) + C1 if n > 2

We have ignored the floor() part as it doesn't matter here if it's a floor or ceiling.

Recursive expression for the above program will be.

T(n) = 2T(n-1) + c
T(1) = c1.

Let us solve it.

By Case 1 of the Master Method, we have T(n) = θ(n ^ (log5(3))). [^ is for power]

Change of variables: let m = lg n. Recurrence becomes S(m) = S(m/2) + θ(lgm). Case 2 of master’s theorem applies, so T(n) = θ( (log Log n) ^ 2).

We have T (2^k) = 3  T (2^k-1) + 1 = 3²  T (2^k-2) + 1 + 3 = 3³  T (2^k-3) + 1 + 3 + 9 . . . (k steps of recursion (recursion depth)) = 3^k  T (2^k-k) + (1 + 3 + 9 + 27 + ... + 3^k-1) = 3^k + (( 3^k - 1)/2) = ((2 * 3^k) + 3^k - 1)/2 = ((3 * 3^k) - 1)/2 = (3^k+1 - 1)/2 Hence, B is the correct choice.

The recurrence is

T(x, y) = Θ(x+y) + T(x/2, y/2)

It can be written as below.

T(x, y) = Θ(x+y) + Θ((x+y)/2) + Θ((x+y)/4) + Θ((x+y)/8) .....
T(x, y) = Θ((x+y) + (x+y)/2 + (x+y)/4 + (x+y)/8 ..... )

The above expression forms a geometric series with ratio as 2 and starting element as (x+y)/2 T(x, y) is upper bounded by Θ(x+y) as sum of infinite series is 2(x+y). It is lower bounded by (x+y)

The value of sine function varies from -1 to 1.

For sin = -1 or any other negative value, I becomes false.

For sin = 1 or any other negative value, II becomes false