GATE CS 2006 Q15 — Asymptotic Worst Case Time and Space Complexity

Consider the following recurrence relations: For all $n>1$, $$\begin{array}{c} T_{1}(n)=4 T_{1}\left(\frac{n}{2}\right)+T_{2}(n) \\ T_{2}(n)=5 T_{2}\left(\frac{n}{4}\right)+\Theta\left(\log _{2} n\right) \end{array}$$ Assume that for all $n \leq 1, T_{1}(n)=1$ and $T_{2}(n)=1$. Which one of the following options is correct?

Consider the recursive functions represented by the following code segment: int bar(int n) { if (n == 1) return 0; else return 1 + bar(n/2); } int foo(int n) { if (n == 1) return 1; else return 1 + foo(bar(n)); } The smallest positive integer n for which $\mathrm{f} \circ \circ(\mathrm{n})$ returns $5$ is $\_\_\_\_$. (answer in integer) Note: Ignore …

Consider the following functions, where $n$ is a positive integer. $$n^{1 / 3}, \log (n), \log (n!), 2^{\log (n)}$$ Which one of the following options lists the functions in increasing order of asymptotic growth rate? Note: Assume the base of log to be $2$.

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $\Theta(n)$?

Consider an array $A$ of integers of size $n$. The indices of $A$ run from $1$ to $n$. An algorithm is to be designed to check whether $A$ satisfies the condition given below. $\forall i, j \in\{1, \ldots, n-1\}$ such that $i>j,(A[i+1]-A[i])>(A[j+1]-A[j])$ Which one of the following gives the worst case time complexity of the fastest …

Consider the following recurrence relation: $$T(n)=2 T(n-1)+n 2^{n} \text{ for } n>0, \quad T(0)=1$$ Which ONE of the following options is CORRECT?