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
Recent questions tagged timecomplexity
+2
votes
1
answer
1
ISRO202036
What is the complexity of the following code? sum=0; for(i=1;i<=n;i*=2) for(j=1;j<=n;j++) sum++; Which of the following is not a valid string ? $O(n^2)$ $O(n\log\ n)$ $O(n)$ $O(n\log\ n\log\ n)$
asked
Jan 13
in
Algorithms
by
Satbir
Boss
(
24.2k
points)

248
views
isro2020
algorithms
timecomplexity
normal
+1
vote
1
answer
2
IIIT BLR TEST 1 : ALGORITHMS 3
Given an array of ( both positive and negative ) integers, $a_0,a_1,….a_{n1}$ and $l, 1<l<n$. Design a linear time algorithm to compute the maximum product subarray, whose length is atmost $l$.
asked
Aug 27, 2019
in
Algorithms
by
Shaik Masthan
Veteran
(
65.8k
points)

245
views
iiit_blr
test_1
arrays
timecomplexity
0
votes
1
answer
3
IIIT BLR TEST 1 : ALGORITHMS 1
Solve the following recursions ( in terms of Θ ). T(0) = T(1) = Θ(1) in all of the following. $T(n) = n + \frac{1}{n}\sum_{i=0}^{i=n1}T(i)$ $T(n) = n + \frac{2}{n}\sum_{i=0}^{i=n1}T(i)$ $T(n) = n + \frac{4}{n}\sum_{i=0}^{i=n/2}T(i)$ $T(n) = n + \frac{40}{n}\sum_{i=0}^{i=n/5}T(i)$
asked
Aug 27, 2019
in
Algorithms
by
Shaik Masthan
Veteran
(
65.8k
points)

144
views
iiit_blr
test_1
algorithms
timecomplexity
0
votes
1
answer
4
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

74
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
2
answers
5
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

38
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
1
answer
6
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

26
views
cormen
algorithms
quicksort
timecomplexity
descriptive
+1
vote
1
answer
7
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

58
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
1
answer
8
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

55
views
cormen
algorithms
recurrence
timecomplexity
descriptive
0
votes
1
answer
9
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

42
views
cormen
algorithms
sorting
timecomplexity
descriptive
0
votes
1
answer
10
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

35
views
algorithms
cormen
timecomplexity
descriptive
0
votes
2
answers
11
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

70
views
cormen
algorithms
timecomplexity
descriptive
0
votes
0
answers
12
Is each and every NP complete problem (polynomially) reduced to each and every another NP complete problem?
asked
Jun 13, 2019
in
Theory of Computation
by
commenter commenter
Active
(
1.6k
points)

49
views
pnpnpcnph
theoryofcomputation
timecomplexity
0
votes
1
answer
13
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, 2019
in
Algorithms
by
lolster
(
237
points)

114
views
algorithms
mastertheorem
timecomplexity
asymptoticnotations
+1
vote
0
answers
14
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, 2019
in
Algorithms
by
kshitij
(
295
points)

139
views
algorithms
timecomplexity
recurrence
0
votes
1
answer
15
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, 2019
in
Algorithms
by
shubhojit1412
(
5
points)

168
views
asymptoticnotations
algorithms
timecomplexity
growthrate
+1
vote
3
answers
16
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, 2019
in
Algorithms
by
Jyoti Kumari97
(
187
points)

810
views
timecomplexity
algorithms
recurrenceeqation
+3
votes
0
answers
17
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, 2019
in
Algorithms
by
srestha
Veteran
(
119k
points)

254
views
algorithms
madeeasytestseries
timecomplexity
0
votes
0
answers
18
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, 2019
in
Compiler Design
by
srestha
Veteran
(
119k
points)

109
views
infixpostfix
algorithms
timecomplexity
0
votes
1
answer
19
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, 2019
in
Algorithms
by
srestha
Veteran
(
119k
points)

159
views
algorithms
timecomplexity
recurrenceeqation
+1
vote
0
answers
20
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, 2019
in
Algorithms
by
toxicdesire
Active
(
2k
points)

179
views
timecomplexity
algorithms
goscreeningtest
+3
votes
1
answer
21
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, 2019
in
Algorithms
by
srestha
Veteran
(
119k
points)

382
views
madeeasytestseries
algorithms
timecomplexity
+1
vote
1
answer
22
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, 2019
in
Programming
by
manikgupta123
(
81
points)

173
views
iiithpgee
timecomplexity
binaryheap
0
votes
1
answer
23
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, 2019
in
DS
by
manikgupta123
(
81
points)

153
views
iiithpgee
graphtheory
timecomplexity
+2
votes
1
answer
24
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, 2019
in
Programming
by
manikgupta123
(
81
points)

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

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

124
views
asymptoticnotations
timecomplexity
0
votes
0
answers
27
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, 2019
in
Algorithms
by
sumitr
(
235
points)

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

120
views
timecomplexity
algorithms
0
votes
2
answers
29
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, 2019
in
Algorithms
by
Tanuj Guha Thakurta
(
175
points)

84
views
timecomplexity
asymptoticnotations
0
votes
0
answers
30
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, 2019
in
Algorithms
by
syncronizing
Junior
(
835
points)

163
views
timecomplexity
algorithms
recurrence
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged timecomplexity
Recent Blog Comments
Has anyone else challenged the questions on...
@nkg_master9  For getting selected for the...
Nowhere it's mentioned.
@bond  Is it mentioned that you have to score at...
I think cutoff won't cross 85
50,737
questions
57,385
answers
198,548
comments
105,365
users