The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged timecomplexity
0
votes
1
answer
1
Cormen Edition 3 Exercise 7.4 Question 4 (Page No. 184)
Show that RANDOMIZEDQUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.
asked
Jun 28
in
Algorithms
by
akash.dinkar12
Boss
(
40.9k
points)

11
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
0
answers
2
Cormen Edition 3 Exercise 7.4 Question 2 (Page No. 184)
Show that quicksort’s bestcase running time is $\Omega(n\ lg\ n)$.
asked
Jun 28
in
Algorithms
by
akash.dinkar12
Boss
(
40.9k
points)

9
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
0
answers
3
Cormen Edition 3 Exercise 7.2 Question 3 (Page No. 178)
Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
40.9k
points)

7
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
1
answer
4
Cormen Edition 3 Exercise 7.2 Question 2 (Page No. 178)
What is the running time of QUICKSORT when all elements of the array $A$ have the same value?
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
40.9k
points)

20
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
1
answer
5
Cormen Edition 3 Exercise 2.3 Question 3 (Page No. 39)
Use mathematical induction to show that when $n$ is an exact power of $2$, the solution of the recurrence $T(n) = \begin{cases} 2 \text{, if n=2, } \\2T(n/2)+n \text{, if n=$2^k$,for k >1} \end{cases}$ is $T(n) = n\ lg\ n$.
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
40.9k
points)

18
views
cormen
algorithms
recurrence
timecomplexity
descriptive
0
votes
1
answer
6
Cormen Edition 3 Exercise 2.3 Question 4 (Page No. 38)
We can express the insertion sort as a recursive procedure as follows.In order to sort $A[1\dots n]$, we recursively sort $A[1 \dots n1]$ and then insert $A[n]$ into the sorted array $A[1 \dots n1]$. Write a recurrence for the running time of this recursive version of insertion sort.
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
40.9k
points)

14
views
cormen
algorithms
sorting
timecomplexity
descriptive
0
votes
1
answer
7
Cormen Edition 3 Exercise 2.2 Question 2 (Page No. 29)
Consider sorting $n$ numbers stored in an array $A$ by first finding the smallest element of $A$ and exchanging it with the element in $A[1]$. Then find the second smallest element of $A$ ... , rather than for all n elements? Give the bestcase and worstcase running times of selection sort in $\Theta$notation
asked
Jun 25
in
Algorithms
by
akash.dinkar12
Boss
(
40.9k
points)

7
views
algorithms
cormen
timecomplexity
descriptive
0
votes
0
answers
8
Cormen Edition 3 Exercise 2.2 Question 1 (Page No. 29)
Express the function $n^3/1000 100n^2100n+3$ in terms of $\Theta$ notation.
asked
Jun 25
in
Algorithms
by
akash.dinkar12
Boss
(
40.9k
points)

14
views
cormen
algorithms
timecomplexity
descriptive
0
votes
0
answers
9
Is each and every NP complete problem (polynomially) reduced to each and every another NP complete problem?
asked
Jun 13
in
Theory of Computation
by
commenter commenter
(
179
points)

38
views
pnpnpcnph
theoryofcomputation
timecomplexity
0
votes
1
answer
10
Master's Theorem: Validity of Format
How to check if a given recurrence relation is in a format that is valid to apply Master’s Theorem? Also, how to distinguish between Master’s Theorem and extended Master’s Theorem?
asked
Jun 12
in
Algorithms
by
lolster
(
223
points)

67
views
algorithms
mastertheorem
timecomplexity
asymptoticnotations
+1
vote
0
answers
11
GATE1999
Consider the following algorithms. Assume, procedure $A$ and procedure $B$ take $O(1)$ and $O(1/n)$ unit of time respectively. Derive the time complexity of the algorithm in $O$ notation. algorithm what (n) begin if n = 1 then call A else begin what (n1); call B(n ... $c$ So complexity should be $O(1)$. But answer is $O(n)$.What I am doing wrong?
asked
Jun 4
in
Algorithms
by
kshitij
(
105
points)

94
views
algorithms
timecomplexity
recurrence
0
votes
1
answer
12
Asymptotic Notation theta property
If $T1(n) = \Theta(f(n))$ & $T2(n) = \Theta(f(n))$ Then, Is $T1(n) + T2(n) = O(f(n))$ If yes, then how?
asked
May 26
in
Algorithms
by
shubhojit1412
(
5
points)

101
views
asymptoticnotations
algorithms
timecomplexity
growthrate
+1
vote
2
answers
13
Made easy Workbook 2020
Question: $T(1)=1$ $T(n) = 2 T(n  1) + n$ evaluates to? Can anyone solve it by substitution method? Given answer $T(n) = 2^{n+1}  (n+2)$ How?
asked
May 25
in
Algorithms
by
Jyoti Kumari97
(
181
points)

136
views
timecomplexity
algorithms
recurrenceeqation
+1
vote
0
answers
14
Made Easy Test Series:AlgorithmTime Complexity
Consider a procedure $find()$ which take array of $n$ integers as input, and produce pair of element of array whose difference is not greater than the difference of any other pair of element of that array. Which of the following represent ... Here we need to sort first and then need to compare adjacent element right?? Then what will be complexity??
asked
May 18
in
Algorithms
by
srestha
Veteran
(
112k
points)

87
views
algorithms
madeeasytestseries
timecomplexity
0
votes
0
answers
15
Made Easy Test Series: AlgorithmReverse Polish Notation
Consider the neworder strategy for traversing a binary tree: Visit the root Visit the right subtree using neworder Visit the left subtree using neworder The neworder traversal of expression tree corresponding to the reverse polish expression 3 4 * 5 – 2 ^ 6 7 * 1 + – What will be expression, any procedure for it??
asked
May 16
in
Compiler Design
by
srestha
Veteran
(
112k
points)

77
views
infixpostfix
algorithms
timecomplexity
0
votes
1
answer
16
Made Easy Test Series:AlgorithmRecurrence Relation
What is the solution of recurrence relation $T\left ( n \right )=T\left ( n1 \right )+n$
asked
May 10
in
Algorithms
by
srestha
Veteran
(
112k
points)

96
views
algorithms
timecomplexity
recurrenceeqation
+1
vote
0
answers
17
GO screening test
Which one of the following notations is most relevant for finding the best algorithm for a problem? (A) $o(f(n))$ (B) $O(f(n))$ (C) $\omega (f(n))$ (D) $ \Omega (f(n))$
asked
May 9
in
Algorithms
by
toxicdesire
Junior
(
855
points)

128
views
timecomplexity
algorithms
goscreeningtest
0
votes
1
answer
18
Made Easy Test Series:Time Complexity
Consider the following program: int Bar(int n){ if(n<2) return; } else{ int sum=0; int i,j; for(i=1;i<=4;i++) Bar(n/2); for(i=1;i<=n;i++){ for(j=1;j<=i;j++){ sum=sum+1; } } } Now consider the following ... $Bar\left ( n \right )$ is $O \left ( n^{3}logn^{2} \right )$ How many statements are correct________________
asked
May 7
in
Algorithms
by
srestha
Veteran
(
112k
points)

220
views
madeeasytestseries
algorithms
timecomplexity
+1
vote
1
answer
19
IIIT PGEE 2019
What is the time complexity to delete an arbitrary node from binary heap? O(n) O(log n) O(1) O(n log n)
asked
Apr 29
in
Programming
by
manikgupta123
(
75
points)

127
views
iiithpgee
timecomplexity
binaryheap
0
votes
1
answer
20
IIIT PGEE 2019
Which of the following gives O(1) complexity if we want to check whether an edge exists between two given nodes in a graph? Adjacency List Adjacency Matrix Incidence Matrix None of these
asked
Apr 29
in
DS
by
manikgupta123
(
75
points)

114
views
iiithpgee
graphtheory
timecomplexity
+2
votes
1
answer
21
IIIT PGEE 2019
What is the time complexity for insertion in binary tree in worst case? O(1) O(log n) O(n) O(n log n)
asked
Apr 29
in
Programming
by
manikgupta123
(
75
points)

137
views
iiithpgee
binarytree
timecomplexity
+1
vote
1
answer
22
If there is an $\rm NP$complete language $L$ whose complement is in $\rm NP$, then...
asked
Apr 20
in
Theory of Computation
by
Rhythm
(
189
points)

99
views
theoryofcomputation
timecomplexity
pnpnpcnph
+1
vote
0
answers
23
Find Asymptotic upper bound (http://www.csd.uwo.ca/~moreno/CS433CS9624/Resources/master.pdf)
asked
Apr 19
in
Algorithms
by
Mk Utkarsh
Boss
(
34.5k
points)

98
views
asymptoticnotations
timecomplexity
0
votes
0
answers
24
Algorithm Time ComplexitySelf Doubt
What is the best case and worst case of the algorithm? And when will best case and worst case will happen?? int main() { for(i=1 ; i<=n ; i++) { if(n%i == 0) { for(j=1 ; j<=n ; j++) { printf("Hello"); } } } }
asked
Apr 10
in
Algorithms
by
sumitr
(
235
points)

147
views
algorithms
timecomplexity
selfdoubt
0
votes
1
answer
25
Time complexity
Please help to find the time complexity of this loop. void main() { int n; while(n>=1) { n=n2; } }
asked
Mar 19
in
Algorithms
by
Devshree Dubey
Boss
(
13.7k
points)

90
views
timecomplexity
algorithms
0
votes
2
answers
26
Self doubt
O(n1)+O(n)=O(n) O(n/2)+O(n)=O(n) but O(1)+O(2)+O(3)+...+O(n)=O(n(n+1)/2)=O(n^2) why?
asked
Mar 19
in
Algorithms
by
Tanuj Guha Thakurta
(
151
points)

61
views
timecomplexity
asymptoticnotations
0
votes
0
answers
27
Time complexity
Is this the correct way to solve ? Q) int algorithm(int n) { int sum =0;k,j; for (k=0;k<n/2;k++) for(j=0;j<10;j++) sum++; return 4*algorithm(n/2)*algorithm(n/2)+algorithm(n/2)*algorithm(n/2) }
asked
Mar 15
in
Algorithms
by
syncronizing
Junior
(
789
points)

122
views
timecomplexity
algorithms
recurrence
0
votes
1
answer
28
JEST Sample Question 1d
T (n) = T (n/2) + 2; T (1) = 1 When n is a power of 2, the correct expression for T (n) is: (A) 2(log n + 1) (B) 2 log n (C) log n + 1 (D)2 log n + 1
asked
Feb 15
in
Algorithms
by
sripo
Active
(
2.3k
points)

110
views
jest
algorithms
timecomplexity
0
votes
1
answer
29
JEST Sample Question4
A tournament is a directed graph in which there is exactly one directed edge between every pair of vertices. Let Tn be a tournament on n vertices. (a) Use induction to prove the following statement: Tn has a directed hamiltonian path (a directed ... or a simple description of the steps in the algorithm, will suffice. What is the worst case time complexity of your algorithm?
asked
Feb 15
in
Algorithms
by
sripo
Active
(
2.3k
points)

61
views
jest
algorithms
timecomplexity
0
votes
1
answer
30
JEST Sample Question5
Describe two different data structures to represent a graph. For each such representation, specify a simple property about the graph that can be more efficiently checked in that representation than in the other representation. Indicate the worst case time required for verifying both of your properties in either representation.
asked
Feb 15
in
Algorithms
by
sripo
Active
(
2.3k
points)

33
views
jest
algorithms
timecomplexity
Page:
1
2
3
4
5
6
...
27
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
Recent Posts
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
My journey from Wipro to an IISc student  GATE 2019
Interview Experience at IITPalakkad
Follow @csegate
Recent questions tagged timecomplexity
Recent Blog Comments
Hi, the previous email was sent to only those who...
@kriti05 can you please tell me when did you got...
It was said that there will be an address...
sir .I recvd a mail which states "Your...
49,808
questions
54,489
answers
188,271
comments
74,682
users