Register
Webpage for Algorithms

Recent questions tagged algorithms

17.0k
views
4 answers
46 votes
GATE CSE 2008 | Question: 43
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let ... \leq 2T(4n/5) + n$T(n) \leq 2T(n/2) + n$
User Avatar
37.9k
views
7 answers
79 votes
GATE CSE 2008 | Question: 40
The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is$\Theta(n)$\Theta(\log n)$\Theta(\log^*n)$\Theta(1)$
User Avatar
17.0k
views
5 answers
40 votes
GATE CSE 2008 | Question: 39
Consider the following functions:$f(n) = 2^n$g(n) = n!$h(n) = n^{\log n}$Which of the following statements about the asymptotic behavior of $f(n)$, $g(n)$ and ...
User Avatar
36.4k
views
6 answers
31 votes
GATE CSE 2008 | Question: 19
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is:$\text{MNOPQR}$\text{NQMPOR}$\text{QMNPRO}$\text{QMNPOR}$
User Avatar
14.0k
views
6 answers
28 votes
GATE CSE 2008 | Question: 7
The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity$\Theta(n)$\Theta(m)$\Theta(m+n)$\Theta(mn)$
User Avatar
22.2k
views
5 answers
48 votes
GATE CSE 2008 | Question: 84
Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y[10] , int x) { int i, j, k; ... $ 2 < x < 20$ and $x$ is even
User Avatar
25.0k
views
8 answers
107 votes
GATE CSE 2003 | Question: 66
The cube root of a natural number $n$ is defined as the largest natural number $m$ such that $(m^3 \leq n)$ . The complexity of computing the cube root of $n$ ($n$ is ... some constant $k > 0.5$, but not $O( (\log \log n)^{0.5} )$
User Avatar
904
views
1 answers
1 votes
What is the time complexity ?
What is the time complexity?main() { n=2^2^k, k>0 for(i = 1 to n) { j=2 while(j ≤ n) { j=j^2 } } }
User Avatar
2.6k
views
2 answers
5 votes
What is the time complexity?
double foo(int n) { int i; double sum; if(n == 0) { return 1.0; } else { sum = 0.0; for(i = 0; i < n; i++) { sum += foo(i); } return sum; } }The time complexity of the above code is?
User Avatar
3.0k
views
2 answers
5 votes
Is the following statement valid? $$\log(n!) = \Theta(n \log n)$$
User Avatar
1.3k
views
1 answers
5 votes
max min
Simple linear search to find max min algomaxmin(a,n,max,min) { max=min=a[1]; for i=2 to n do { if a[i]>max then max:=a[i]; else if ... n/2 elements2.Average case complexity of the above algo if the first condition fails 1/2 timesplz xplain
User Avatar
32.4k
views
9 answers
81 votes
GATE CSE 2013 | Question: 44
Consider the following operation along with Enqueue and Dequeue operations on queues, where $k$ is a global parameter.MultiDequeue(Q){ m = k while (Q is not empty) and (m > 0) ... $Θ(n + k)$Θ(nk)$Θ(n^2)$
User Avatar
14.7k
views
4 answers
43 votes
GATE CSE 2012 | Question: 18
Let $W(n) $ and $A(n)$ denote respectively, the worst case and average case running time of an algorithm executed on an input of size $n$ ... $A(n) = \text{o} (W(n))$
User Avatar
16.0k
views
3 answers
35 votes
GATE CSE 2012 | Question: 16
The recurrence relation capturing the optimal execution time of the $Towers \ of \ Hanoi$ problem with $n$ discs is$T(n) = 2T(n − 2) + 2$T (n) = 2T(n − 1) + n$T (n) = 2T(n/2) + 1$T (n) = 2T(n − 1) + 1$
User Avatar
Page: