GATE CS Asymptotic Worst Case Time and Space Complexity questions

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?

Given an integer array of size $N$, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is

Consider the following recurrence relation: $T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text{ for } n \geq 1, \\ 1 \quad \text{ for } n=1\end{array}\right.$ Which one of the following options is CORRECT?

​​​​​Let $\text{T(n)}$ be the recurrence relation defined as follows: $$\begin{array}{l} T(0)=1, \\ T(1)=2, \text{ and } \\ T(n)=5 T(n-1)-6 T(n-2) \text{ for } n \geq 2 \end{array}$$ Which one of the following statements is TRUE?

Let $f$ and $g$ be functions of natural numbers given by $f(n)=n$ and $g(n)=n^{2}.$ Which of the following statements is/are $\text{TRUE}?$

Consider functions $\textsf{Function\_1}$ and $\textsf{Function\_2}$ expressed in pseudocode as follows: Function_1 while n>1 do for i=1 to n do x = x + 1; end for n = ⌊n/2⌋; end while Function_2 for i = 1 to 100 * n do x = x + 1; end for Let $f_{1}(n)$ and $f_{2}(n)$ denote the number of times the statement $\textsf{“x = x + 1”}$ is executed in …

Which one of the following statements is $\text{TRUE}$ for all positive functions $f(n)?$

Consider the following three functions. $$f_1=10^n\quad f_2=n^{\log n}\quad f_3=n^{\sqrt {n}}$$ Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

Consider the following recurrence relation. $$T\left ( n \right )=\left\{\begin{array} {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.$$ Which one of the following options is correct?

Consider the following $\text{ANSI C}$ function: int SimpleFunction(int Y[], int n, int x) { int total = Y[0], loopIndex; for (loopIndex=1; loopIndex<=n-1; loopIndex++) total=x*total +Y[loopIndex]; return total; } Let $\textsf{Z}$ be an array of $10$ elements with $\textsf{Z}[i]=1$, for all $i$ such that $0 \leq i \leq 9$. The value returned …

Consider the following $\text{ANSI C}$ function: int SomeFunction (int x, int y) { if ((x==1) || (y==1)) return 1; if (x==y) return x; if (x > y) return SomeFunction(x-y, y); if (y > x) return SomeFunction (x, y-x); } The value returned by $\textrm{SomeFunction(15, 255)}$ is __________

For constants $a \geq 1$ and $b>1$, consider the following recurrence defined on the non-negative integers: $$T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n)$$ Which one of the following options is correct about the recurrence $T(n)$?

Consider the following $\text{ANSI C}$ program #include <stdio.h> int foo(int x, int y, int q) { if ((x<=0) && (y<=0)) return q; if (x<=0) return foo(x, y-q, q); if (y<=0) return foo(x-q, y, q); return foo(x, y-q, q) + foo(x-q, y, q); } int main( ) { int r = foo(15, 15, 10); printf(“%d”, r); return 0; } The output of the program …

For parameters $a$ and $b$, both of which are $\omega(1)$, $T(n) = T(n^{1/a})+1$, and $T(b)=1$. Then $T(n)$ is

Consider the following C functions. int tob (int b, int* arr) { int i; for (i = 0; b>0; i++) { if (b%2) arr [i] = 1; else arr[i] = 0; b = b/2; } return (i); } int pp(int a, int b) { int arr[20]; int i, tot = 1, ex, len; ex = a; len = tob(b, arr); for (i=0; i<len ; i++) { if (arr[i] ==1) tot = tot * ex; ex= ex*ex; } return (tot) ; } The value returned …