Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Year
Exams
Recent questions tagged algorithms
0
votes
1
answer
Time complexity of below program
what should be the time complexity of below program anyone can anyone please explain for(i=1;i<=n:++i) { for(i=1;i<=n^2:++i) { for(i=1;i<=n^3:++i) { x=y+z; } } }
asked
May 23
in
Programming
by
Sumit goyal 2
(
7
points)

11
views
algorithms
#recurrencerelations
#timecomplexity
0
votes
0
answers
Geeks for Geeks Topic Test
Which of the following is not true about comparisonbased sorting algorithms. The minimum possible time complexity of a comparisonbased sorting algorithm is O(N log N) for a random input array. Any comparisonbased sorting algorithm can be made stable by using ... . Heap Sort is not a comparisonbased sorting algorithm. Choose the correct option. 1,2. 2,4. 4. 2.
asked
May 16
in
Algorithms
by
ramcharantej_24
(
22
points)

10
views
algorithms
sorting
#gate
0
votes
0
answers
Geeks For Geeks Topic Question
Consider the problem of computing minmax in an unsorted array where min and max are minimum and maximum elements of an array. Algorithm A1 can compute minmax in a1 comparisons using divide and conquer. Algorithm A2 can compute minmax in a2 comparisons by ... and a2 considering the worstcase scenarios? a1 < a2. a2 > a1. a1 = a2. Depends on the input.
asked
May 16
in
Algorithms
by
ramcharantej_24
(
22
points)

3
views
algorithms
divideandconquer
#gate2017mock
0
votes
0
answers
Tower of Hanoi
There are n disks of different sizes and three pegs. Initially, all the disks are on the first peg in order of size, the largest on the bottom and the smallest on top. The object is to transfer all the disks to the third peg. Only one disk can be moved ... a disk on the middle peg or move a disk from that peg. Write an algorithm that solves the problem in the minimum number of moves.
asked
May 8
in
Algorithms
by
sumitsehgal
(
8
points)

9
views
algorithms
datastructures
0
votes
0
answers
Tower of hanoi
There are n disks of different sizes and three pegs. Initially, all the disks are on the first peg in order of size, the largest on the bottom and the smallest on top. The object is to transfer all the disks to the third peg. Only one disk can be moved ... a disk on the middle peg or move a disk from that peg. Write an algorithm that solves the problem in the minimum number of moves.
asked
May 8
in
Algorithms
by
sumitsehgal
(
8
points)

6
views
algorithms
datastructures
0
votes
0
answers
Find minimum weight cycle in an undirected graph please explain time complexity by other than dijkstra’s shortest path
asked
Apr 30
in
Algorithms
by
abhishek tiwary
(
18
points)

13
views
algorithms
0
votes
1
answer
Cormen Excersice 4, Question 4.41
Solve the Given Recurrence using the Substitution method (in book it was Recursion Tree method) T(n) = 3T(n/2) + n
asked
Apr 29
in
Algorithms
by
ramcharantej_24
(
22
points)

31
views
cormen
algorithms
recurrence
divideandconquer
0
votes
0
answers
Find time complexity of T(n) = 2*T(n1) + 3*T(n2)
asked
Apr 23
in
Algorithms
by
roh
(
17
points)

13
views
algorithms
timecomplexity
#recurrencerelations
#timecomplexity
0
votes
0
answers
Complexity analysis of algorithms
What is the time complexity of the below algorithm: sum = 0; for(i=0; i<=n; i++){ for(j=1; j<= i; j=j*2){ sum = sum + j } }
asked
Apr 21
in
Algorithms
by
roh
(
17
points)

19
views
algorithms
timecomplexity
0
votes
0
answers
GATE2014139 Video Solution
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

7
views
gate20141
algorithms
numericalanswers
normal
minimummaximum
videosolution
0
votes
0
answers
GATE2016139 Video Solution
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight spanning tree of $G$ can have is __________
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate20161
algorithms
spanningtree
normal
numericalanswers
videosolution
0
votes
0
answers
GATE200715,ISRO201626 Video Solution
Consider the following segment of Ccode: int j, n; j = 1; while (j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any $n > 0$ is: $\lceil \log_2n \rceil +1$ $n$ $\lceil \log_2n \rceil$ $\lfloor \log_2n \rfloor +1$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2007
algorithms
timecomplexity
normal
isro2016
videosolution
0
votes
0
answers
GATE200651, ISRO201634 Video Solution
Consider the following recurrence: $ T(n)=2T\left ( \sqrt{n}\right )+1,$ $T(1)=1$ Which one of the following is true? $ T(n)=\Theta (\log\log n)$ $ T(n)=\Theta (\log n)$ $ T(n)=\Theta (\sqrt{n})$ $ T(n)=\Theta (n)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

3
views
algorithms
recurrence
isro2016
gate2006
videosolution
0
votes
0
answers
GATE2014142 Video Solution
Consider the following pseudo code. What is the total number of multiplications to be performed? D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3 Half of the product of the $3$ consecutive integers. Onethird of the product of the $3$ consecutive integers. Onesixth of the product of the $3$ consecutive integers. None of the above.
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate20141
algorithms
timecomplexity
normal
videosolution
0
votes
0
answers
GATE2014314 Video Solution
You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is $O(n^2)$ $O(n \log n)$ $\Theta(n\log n)$ $O(n^3)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

3
views
gate20143
algorithms
sorting
easy
videosolution
0
votes
0
answers
GATE19962.13, ISRO201628 Video Solution
The average number of key comparisons required for a successful search for sequential search on $n$ items is $\frac{n}{2}$ $\frac{n1}{2}$ $\frac{n+1}{2}$ None of the above
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate1996
algorithms
easy
isro2016
searching
videosolution
0
votes
0
answers
GATE2016140 Video Solution
$G=(V, E)$ is an undirected simple graph in which each edge has a distinct weight, and $e$ is a particular edge of $G$. Which of the following statements about the minimum spanning trees $(MSTs)$ of $G$ is/are TRUE? If $e$ is the lightest edge of some cycle in ... of some cycle in $G$, then every MST of $G$ excludes $e$. I only. II only. Both I and II. Neither I nor II.
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate20161
algorithms
spanningtree
normal
videosolution
0
votes
0
answers
GATE201330 Video Solution
The number of elements that can be sorted in $\Theta(\log n)$ time using heap sort is $\Theta(1)$ $\Theta(\sqrt{\log} n)$ $\Theta(\frac{\log n}{\log \log n})$ $\Theta(\log n)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate2013
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE200429 Video Solution
The tightest lower bound on the number of comparisons, in the worst case, for comparisonbased sorting is of the order of $n$ $n^2$ $n \log n$ $n \log^2n$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2004
algorithms
sorting
asymptoticnotations
easy
videosolution
0
votes
0
answers
GATE201344 Video Solution
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) { Dequeue(Q) m = m – 1 } } What is the worst case time complexity of a sequence of $n$ queue operations on an initially empty queue? $Θ(n)$ $Θ(n + k)$ $Θ(nk)$ $Θ(n^2)$
asked
Apr 19
in
DS
by
admin
(
3.6k
points)

1
view
gate2013
datastructures
algorithms
normal
queues
videosolution
0
votes
0
answers
GATE2016111 Video Solution
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate20161
algorithms
graphalgorithms
normal
numericalanswers
videosolution
0
votes
0
answers
GATE200840 Video Solution
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)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

3
views
gate2008
normal
algorithms
timecomplexity
videosolution
0
votes
0
answers
GATE200366 Video Solution
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 represented by binary notation) is $O(n)$ but not $O(n^{0.5})$ $O(n^{0.5})$ ... constant $m>0$ $O( (\log \log n)^k )$ for some constant $k > 0.5$, but not $O( (\log \log n)^{0.5} )$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate2003
algorithms
timecomplexity
normal
videosolution
0
votes
0
answers
GATE200745 Video Solution
What is the $\text{time complexity}$ of the following recursive function? int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor (sqrt(n))) + n); } $\Theta(n^2)$ $\Theta(n \log_2n)$ $\Theta(\log_2n)$ $\Theta(\log_2\log_2n)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2007
algorithms
timecomplexity
normal
videosolution
0
votes
0
answers
GATE201239 Video Solution
A list of $n$ strings, each of length $n$, is sorted into lexicographic order using the mergesort algorithm. The worst case running time of this computation is $O (n \log n) $ $ O(n^{2} \log n) $ $ O(n^{2} + \log n) $ $ O(n^{2}) $
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate2012
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE2015140 Video Solution
An algorithm performs $(\log N)^{\frac{1}{2}}$ find operations , $N$ insert operations, $(\log N)^{\frac{1}{2}}$ delete operations, and $(\log N)^{\frac{1}{2}}$ decreasekey operations on a set of data items ... if the goal is to achieve the best total asymptotic complexity considering all the operations? Unsorted array Min  heap Sorted array Sorted doubly linked list
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate20151
algorithms
datastructures
normal
timecomplexity
videosolution
0
votes
0
answers
GATE200539 Video Solution
Suppose there are $\lceil \log n \rceil$ sorted lists of $\lfloor n /\log n \rfloor$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure) $O(n \log \log n)$ $\Theta(n \log n)$ $\Omega(n \log n)$ $\Omega\left(n^{3/2}\right)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2005
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE200612 Video Solution
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: Queue Stack Heap BTree
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2006
algorithms
graphalgorithms
easy
videosolution
0
votes
0
answers
GATE201034 Video Solution
The weight of a sequence $a_0,a_1, \dots, a_{n1}$ of real numbers is defined as $a_0+a_1/2+ \dots + a_{n1}/2^{n1}$. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let $X$ denote the ... $X$ is equal to $max(Y, a_0+Y)$ $max(Y, a_0+Y/2)$ $max(Y, a_0 +2Y)$ $a_0+Y/2$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

3
views
gate2010
algorithms
dynamicprogramming
normal
videosolution
0
votes
0
answers
GATE20002.17 Video Solution
Consider the following functions $f(n) = 3n^{\sqrt{n}}$ $g(n) = 2^{\sqrt{n}{\log_{2}n}}$ $h(n) = n!$ Which of the following is true? $h(n)$ is $O(f(n))$ $h(n)$ is $O(g(n))$ $g(n)$ is not $O(f(n))$ $f(n)$ is $O(g(n))$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate2000
algorithms
asymptoticnotations
normal
videosolution
0
votes
0
answers
GATE200744 Video Solution
In the following C function, let $n \geq m$. int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function? $\Theta(\log_2n)$ $\Omega(n)$ $\Theta(\log_2\log_2n)$ $\Theta(\sqrt{n})$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2007
algorithms
timecomplexity
normal
videosolution
0
votes
0
answers
GATE201240 Video Solution
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $S$ and $T$. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex $v$ is updated only when a strictly shorter path to $v$ is discovered. $\text{SDT}$ $\text{SBDT}$ $\text{SACDT}$ $\text{SACET}$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2012
algorithms
graphalgorithms
normal
videosolution
0
votes
0
answers
GATE200482 Video Solution
Let $A[1,\ldots,n]$ be an array storing a bit ($1$ or $0$) at each location, and $f(m)$ is a function whose time complexity is $\Theta(m)$. Consider the following program fragment written in a C like language: counter = 0; for (i=1; i<=n; i++) { if a[i ... The complexity of this program fragment is $\Omega(n^2)$ $\Omega (n\log n) \text{ and } O(n^2)$ $\Theta(n)$ $o(n)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate2004
algorithms
timecomplexity
normal
videosolution
0
votes
0
answers
GATE200654 Video Solution
Given two arrays of numbers $a_{1},...,a_{n}$ and $b_{1},...,b_{n}$ where each number is $0$ or $1$, the fastest algorithm to find the largest span $(i, j)$ such that $ a_{i}+a_{i+1}+\dots+a_{j}=b_{i}+b_{i+1}+\dots+b_{j}$ or ... time in the key comparison mode Takes $\Theta (n)$ time and space Takes $O(\sqrt n)$ time only if the sum of the $2n$ elements is an even number
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate2006
algorithms
normal
algorithmdesign
timecomplexity
videosolution
0
votes
0
answers
GATE19991.14, ISRO201542 Video Solution
If one uses straight twoway merge sort algorithm to sort the following elements in ascending order: $20, \ 47, \ 15, \ 8, \ 9, \ 4, \ 40, \ 30, \ 12, \ 17$ ... $4, \ 8, \ 9, \ 15, \ 20, \ 47, \ 12, \ 17, \ 30, \ 40$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate1999
algorithms
sorting
normal
isro2015
videosolution
0
votes
0
answers
GATE2014238 Video Solution
Suppose $P, Q, R, S, T$ are sorted sequences having lengths $20, 24, 30, 35, 50$ respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate20142
algorithms
sorting
normal
numericalanswers
videosolution
0
votes
0
answers
GATE200652 Video Solution
The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot? $\Theta (n)$ $\Theta (n \log n)$ $\Theta (n^{2})$ $\Theta (n^{3})$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate2006
algorithms
sorting
easy
videosolution
0
votes
0
answers
GATE200614, ISRO201114 Video Solution
Which one of the following in place sorting algorithms needs the minimum number of swaps? Quick sort Insertion sort Selection sort Heap sort
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate2006
algorithms
sorting
easy
isro2011
videosolution
0
votes
0
answers
GATE200750 Video Solution
An array of $n$ numbers is given, where $n$ is an even number. The maximum as well as the minimum of these $n$ numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed? At least $2nc$ comparisons, for some ... $c$ are needed. At most $1.5n2$ comparisons are needed. At least $n\log_2 n$ comparisons are needed None of the above
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2007
algorithms
timecomplexity
easy
videosolution
0
votes
0
answers
GATE200845 Video Solution
Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance to only vertex $a$ only vertices $a, e, f, g, h$ only vertices $a, b, c, d$ all the vertices
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate2008
algorithms
graphalgorithms
normal
videosolution
Page:
1
2
3
4
...
12
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users
Jul 2020
bittujash
6 Points
RavGopal
4 Points
ankeshsingh
2 Points
prakhar123
1 Points
arpit_18
1 Points
pravincesingh
1 Points
Shaik Masthan
1 Points
srestha
1 Points
sameer2009
1 Points
7,525
questions
1,776
answers
10,835
comments
90,464
users