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
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
in
Algorithms
by
Shaik Masthan
Veteran
(
62.4k
points)

116
views
iiit_blr
test_1
arrays
timecomplexity
0
votes
1
answer
2
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
in
Algorithms
by
Shaik Masthan
Veteran
(
62.4k
points)

59
views
iiit_blr
test_1
algorithms
timecomplexity
0
votes
1
answer
3
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
(
41.4k
points)

47
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
1
answer
4
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
(
41.4k
points)

22
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
0
answers
5
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
(
41.4k
points)

13
views
cormen
algorithms
quicksort
timecomplexity
descriptive
+1
vote
1
answer
6
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
(
41.4k
points)

35
views
cormen
algorithms
quicksort
timecomplexity
descriptive
0
votes
1
answer
7
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
(
41.4k
points)

35
views
cormen
algorithms
recurrence
timecomplexity
descriptive
0
votes
1
answer
8
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
(
41.4k
points)

27
views
cormen
algorithms
sorting
timecomplexity
descriptive
0
votes
1
answer
9
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
(
41.4k
points)

15
views
algorithms
cormen
timecomplexity
descriptive
0
votes
2
answers
10
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
(
41.4k
points)

37
views
cormen
algorithms
timecomplexity
descriptive
0
votes
0
answers
11
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
(
375
points)

44
views
pnpnpcnph
theoryofcomputation
timecomplexity
0
votes
1
answer
12
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
(
233
points)

83
views
algorithms
mastertheorem
timecomplexity
asymptoticnotations
+1
vote
0
answers
13
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
(
127
points)

109
views
algorithms
timecomplexity
recurrence
0
votes
1
answer
14
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)

122
views
asymptoticnotations
algorithms
timecomplexity
growthrate
+1
vote
3
answers
15
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)

206
views
timecomplexity
algorithms
recurrenceeqation
+1
vote
0
answers
16
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
(
114k
points)

111
views
algorithms
madeeasytestseries
timecomplexity
0
votes
0
answers
17
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
(
114k
points)

86
views
infixpostfix
algorithms
timecomplexity
0
votes
1
answer
18
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
(
114k
points)

115
views
algorithms
timecomplexity
recurrenceeqation
+1
vote
0
answers
19
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
(
999
points)

142
views
timecomplexity
algorithms
goscreeningtest
0
votes
1
answer
20
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
(
114k
points)

264
views
madeeasytestseries
algorithms
timecomplexity
+1
vote
1
answer
21
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)

140
views
iiithpgee
timecomplexity
binaryheap
0
votes
1
answer
22
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)

125
views
iiithpgee
graphtheory
timecomplexity
+2
votes
1
answer
23
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)

154
views
iiithpgee
binarytree
timecomplexity
+1
vote
1
answer
24
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)

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

110
views
asymptoticnotations
timecomplexity
0
votes
0
answers
26
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)

167
views
algorithms
timecomplexity
selfdoubt
0
votes
1
answer
27
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)

100
views
timecomplexity
algorithms
0
votes
2
answers
28
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
(
155
points)

71
views
timecomplexity
asymptoticnotations
0
votes
0
answers
29
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
(
811
points)

135
views
timecomplexity
algorithms
recurrence
0
votes
1
answer
30
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)

116
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
GATE 2020 Application Form Opened!
My GATE Preparation Journey
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Follow @csegate
Recent questions tagged timecomplexity
Recent Blog Comments
will pdfs be uploaded ?
6th...
Sir
4th...
49,984
questions
55,135
answers
190,487
comments
85,112
users