Recent questions tagged algorithms

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

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

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

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

Which of the following statements is/are correct?A.Merge sort always has more number of swaps that comparisonsNumber of comparisons in partition algorithm are same for be...

What is the worst-case time complexity of inserting $n^{2}$ elements into an AVL Tree that already contains $n$ elements?

Which algorithm detects cycles in an undirected graphTopological Sort Prims Union Find Dijkstras

Stooge Sort is a highly inefficient recursive sorting algorithm that works by repeatedly sorting overlapping portions of the array.The algorithm operates as follows:Compa...

Given a permutation $a_1, a_2, \ldots, a_n$, where an inversion is defined as a pair $(i, j)$ such that $i < j$ and $a_i a_j$.If the array has at most $n$ inversions, wh...

GCD time complexity

Given two algorithms to build a Max Heap from an array of n elements: Program $1$ (Bottom-Up): Apply Heapify at each index starting from $\mathrm{n} / 2$ down to $1$Progr...

Time Complexity for finding number of connected components

Time complexity of creating a sorted linked list with n elements. Initially the list is empty.

1. what is the space Complexity of efficient Quick sort algorithem for best case ? in a lecture Reddy Sir Said that it is O(1) is this correct  2.if in the gate exam if t...

How many number of comparison are required in worst case to find out second smallest element of $n$ elements list?$n+\lceil\log n\rceil-1$$n+\lceil\log n\rceil$$\lceil\lo...

Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason RAssertion A: Kruskal's algorithm and Prim's algorithm always produce m...