Recent questions tagged time-complexity

The algorithm $\text{ALGSORT}$ sorts an array of distinct integers using comparisons.The function $\text{MININDEX(V,i,j)}$ returns the position of the smallest element in...

Consider a simple version of Bellman-Ford algorithm where we initialize $\text{distTo}[s]$ to $0$ and the rest of $\text{distTo}[v]$ to $+\infty$. Then fix an order on al...

Consider Dijkstra's algorithm on a graph having $V$ vertices and $E$ edges.Suppose an indexed priority queue is not used.Instead, the tentative distances are stored only ...

Suppose Huffman coding is implemented as follows.Initially, the $n$ symbols are stored in a min priority queue according to their frequencies.The algorithm repeatedly per...

Consider,f1(N): x = 0 for i = 0 to N - 1: x++ return xand,f2(N, R): x = 0 for i = 0 to N - 1: for j = 1; j <= R; j = j + j: x = x + f1(j) return xWhat is the order of gro...

The following running times are observed for a program:$$\begin{array}{|c|c|}\hlineN & \text{Running time} \\\hline1000 & 0.1\text{ seconds} \\2000 & 0.3\text{ seconds} \...

Let $P$ be the problem of sorting $n\geq1$ elements using only comparisons.Consider the class of all comparison-based algorithms that correctly solve $P$.What is the asym...

Consider three recursive algorithms.Algorithm $\mathbf{1}$Divides a problem of size $N$ into two subproblems of size $N/2$ and performs constant additional work.$T_1(N)=2...

Consider the following recursive function $\texttt{Pot}$, which computes $x^n$, where $x$ is real and $n$ is an integer.Pot(x, n): if x == 0: return 0 if n == 0: return 1...

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)$...

Consider the following recursive C function:int fun(int n) { if (n <= 1) { return n; } else { return fun(n - 1) + fun(n - 2); } }What is the time complexity of $\texttt{f...

Consider the following C code:int total = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { total += i * j * k; } } }What is th...

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)$

Consider the following C code:int sum = 0; for (int i = 0; i < n; i++) { sum += i; int k = n; while (k 0) { k = k / 2; } }What is the time complexity?$O(n)$ $O(\log n)$ ...

for optimized merge sort we can say : It is possible to modify the standard algorithm to check if the last element of the left half is less than or equal to the first ele...

Which of the following expressions correctly describe $\mathrm{T}(n) = n^2 \log n$?Select all that apply.$\mathrm{O}(n^2)$$\mathrm{\Theta(n^2)}$$\mathrm{\Omega(n^2)}$$\ma...

Describe the order of growth of the function below.def bonk(n): sum = 0 while n >= 2: sum += n n = n / 2 return sumExponentialLogarithmicLinearQuadratic

Let $A$ be a comparison-based sorting algorithm for sorting an array of length $n$, and let $T$ be the corresponding decision tree.Which of the following are necessarily ...

Recall that the formal definition of Big-O is:$f(n)$ is $\operatorname{O}(g(n))$ if there exist some values $c$, $n_0 0$such that $f(n) \leq c(g(n))$ for all $n \geq n_0...

Which of the following algorithms runs in worst-case $\mathrm{O(n^2)}$ time?Select all that apply.MergeSort, where $\mathrm{n}$ is the number of elements we are sorting.Q...

Let $\text{L}$ contain $\text{N}$ items. What is the Big-O efficiency of the following function?def countSquares(L): count = 0 for item in L: square = item 2 if item != s...

Let $\text{N = n}$. What is the Big-O efficiency of the function below?def f1(n): ret = [] for i in range(n): for j in range(i + 1, n): ret.append(i + j) return ret$\math...

Describe the order of growth of the function below.def bonk(n): sum = 0 while n >= 2: sum += n n = n / 2 return sumConstantLogarithmicLinearQuadraticExponentialNone of th...

What is the order of growth of $\texttt{foo}$ in terms of $\texttt{n}$, where $\texttt{n}$ is the length of $\texttt{lst}$?Assume slicing a list and calling $\texttt{len}...

What is the order of growth of $\texttt{bar}$ in terms of $\texttt{n}$?def bar(n): i, sum = 1, 0 while i <= n: sum += biz(n) i += 1 return sum def biz(n): i, sum = 1, 0 w...

Which of the following is correct order of increasing time complexity of algorithmsTower of Hanoi with $n$ disk.Binary search given $n$ sorted numbers.Heap sort given $n$...

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$, which one of the following options gives the worst...

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 b...

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)+\...