Recent questions tagged goclasses-da-dpp

Suppose array $A[1 \ldots n]$ is sorted in non-decreasing order and it is guaranteed that there exists an index $i$ such that:$A[i] = i$A divide-and-conquer algorithm che...

Solve the recurrence:$T(n) = 4T(n/2) + n^2$$\Theta(n^2)$ $\Theta(n^2\log n)$ $\Theta(n^{\log_2 4})$ $\Theta(n^3)$

Solve the recurrence:$T(n) = 7T(n/2) + n^3$$\Theta(n^{\log_2 7})$ $\Theta(n^3)$ $\Theta(n^3\log n)$ $\Theta(n^2)$

Solve the recurrence:$T(n) = 10T(n/3) + 17n^{1.2}$ $O(n^{1.2})$ $O(n^{\log_3 10})$ $O(n^{1.2}\log n)$ $O(n^3)$

Solve the recurrence:$T(n) = 3T(n/5) + (\log n)^2$ $O((\log n)^2)$ $O(n^{\log_5 3})$ $O(n)$ $O(n\log n)$

Solve the recurrence:$T(n) = T(n/5) + T(4n/5) + O(n)$$O(n)$ $O(n\log n)$ $O(n^2)$ $O(\log n)$

Solve the recurrence:$T(n) = T(n-2) + \log n$Assume $T(n)$ is constant for small $n$.$O(\log n)$ $O(n)$ $O(n\log n)$ $O(n^2)$

For $T(n,n)$, consider:$T(x,c) = \Theta(x)$ for $c \leq 2$$T(x,y) = \Theta(x) + S(x,y/2)$$S(c,y) = \Theta(y)$ for $c \leq 2$$S(x,y) = \Theta(y) + T(x/2,y)$What is the asy...

For $T(n,n)$, consider:$T(x,c) = \Theta(x)$ for $c \leq 2$$T(c,y) = \Theta(y)$ for $c \leq 2$$T(x,y) = \Theta(x) + T(x,y/2)$ What is the asymptotic complexity of $T(n,n)$...

For $T(n,n)$, consider:$T(x,c) = \Theta(x)$ for $c \leq 2$$T(c,y) = \Theta(y)$ for $c \leq 2$$T(x,y) = \Theta(x+y) + T(x/2,y/2)$What is the asymptotic complexity of $T(n,...

Given the following recursive Python function :def fun(n): if n <= 1: return n else: return fun(n - 1) + fun(n - 2)What is the time complexity of $\texttt{fun(n)}$?$O(n)$...

Given the following recursive Python functiondef complex_loops(n): total = 0 for i in range(n): for j in range(n): for k in range(n): total += i * j * k return totalWhat ...

Suppose $f(n) \in \Omega(n^2)$.Classify the following statements:$\text{S1}$. $f(n) \in \Omega(n^3)$ $\text{S2}$. $f(n) \in \Omega(n)$ $\text{S3}$. $f(n) \in O(n)$ $\text...

Arrange the following functions in increasing order of asymptotic growth:$f_1(n) = n^{\sqrt n}$$f_2(n) = 2^n$$f_3(n) = n^{10}\cdot 2^{n/2}$$f_4(n) = \sum_{i=1}^{n}(i+1)$ ...

Arrange the following functions in increasing order of asymptotic growth:$f_1(n) = 2^{2^{1000000}}$$f_2(n) = 2^{100000n}$$f_3(n) = {}^{n}C_{2}$$f_4(n) = n\sqrt n$ $f_1(n)...

Consider the following code:sum = 0 for i in range(n): sum += i k = n while k 0: k = k // 2What is the time complexity?$O(n)$ $O(\log n)$ $O(n \log n)$ $O(n^2)$

Arrange the following functions in increasing order of asymptotic growth:$f_1(n) = \log(n^n)$$f_2(n) = (\log n)^n$$f_3(n) = \log(n^{6006})$$f_4(n) = (\log n)^{6006}$$f_5(...

Suppose we have three functions $f(n)$, $g(n)$, and $h(n)$ such that:$f(n) \in O(g(n))\qquad$ and $\qquad g(n) \in O(h(n))$Which of the following statements are guarantee...

Suppose $g(n) \in \Theta(n^3)$.Which of the following statements are always true?$\text{S1}:$ $g(n) \in O(n^3)$ $\text{S2}:$ $g(n) \in \Theta(n)$ $\text{S3}:$ $g(n) \in \...

Arrange the following functions in increasing order of asymptotic growth:$f_1(n) = n^{0.999999}\log n$ $f_2(n) = 10000000n$ $f_3(n) = 1.000001^n$ $f_4(n) = n^2$ $f_1(n)< ...

Rebalance the following tree so that it becomes a valid AVL tree:What will be the root after rebalancing?$10$ $12$ $16$ $20$

For the keys:$47, 61, 36, 52, 56, 33, 92$consider the hash function:$h(k) = ((10k + 4) \bmod c) \bmod 7$Find the smallest positive integer $c$ such that no collisions occ...

Suppose vector $A$ is a min-heap:$A = [2, 4, 3, 6, 7, 3, 5, 8, 9]$After calling $\texttt{Push(1)}$, what is the final heap array?$[1, 2, 3, 6, 4, 3, 5, 8, 9, 7]$ $[1, 4, ...

A binary tree has:$1000$ nodes in the left subtree $100$ nodes in the right subtreeHow many nodes are processed before the root in preorder, inorder, and postorder traver...

Which of the following statements are true?$\text{S1}$. The worst-case complexity of checking whether an object is present in a hash set is $O(1)$.$\text{S2}$. The worst-...

Given a stack $S$ with $5$ elements from top to bottom as:$2, 4, 6, 8, 10$and an empty queue $Q$.First, remove the elements one by one from $S$ and insert them into $Q$.T...

Insert the following keys into an initially empty AVL tree:$1, 2, 3, 4, 5, 6$What is the root of the final AVL tree?

Insert the keys$47, 61, 36, 52, 56, 33, 92$in order into a hash table of size $7$ using:$h(k) = (10k + 4) \bmod 7$Each slot stores a linked list, and later insertions are...

Suppose numbers between $1$ and $1000$ are stored in a binary search tree. We search for the key $363$.Which of the following sequences could not be the sequence of nodes...

Which of the following statements are true?$\text{S1.}$ Stack operations $\texttt{push}$, $\texttt{pop}$, and $\texttt{isEmpty}$ can be worst-case $O(1)$ for a linked-lis...