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 asymptoticnotations
Notations
+2
votes
1
answer
1
algorithms Asymptotic Notations
asked
Aug 12, 2017
in
Algorithms
by
Pavan Kumar Munnam
Boss
(
10.7k
points)

270
views
asymptoticnotations
algorithms
timecomplexity
+2
votes
1
answer
2
Time Complexity
I think answer should be $O(n^{3})$ but given options are $a.O(n^{4}) b.O(n^{5}) c.O(n^{6}) d.O(n^{7})$ What is the running time of the following code:
asked
Aug 1, 2017
in
Algorithms
by
Manu Thakur
Boss
(
44.1k
points)

217
views
timecomplexity
asymptoticnotations
algorithms
+2
votes
1
answer
3
Cormen 3rd edition (Chapter 4 Divide & Conquer)
Refer Cormen 43 (j) Page no108 Give Asymptotic upper bound of given recurrence using "SUBSTITUTION METHOD" T(n)=n^(1/2) .T(n^(1/2)) +n
asked
Jul 22, 2017
in
Algorithms
by
Veeplob Singh
(
47
points)

198
views
algorithms
asymptoticnotations
functions
recurrenceeqation
+2
votes
1
answer
4
#Backsubstitution
How to solve the following recurrence by back substitution. T(n)= √2 *T(n/2) + c , for n>1 = a for n=1
asked
Jul 21, 2017
in
Algorithms
by
Ashish Subscription
Junior
(
537
points)

391
views
algorithms
timecomplexity
recursion
recurrence
asymptoticnotations
#backsubstitution
0
votes
0
answers
5
CLR 3rd edition , Page no. 49 , second para
"The running time of insertion sort is not Ω($n^{2}$) , since there exists an input for which insertion sort runs in $\Theta (n)$. It is not contradictory , however , to say that the worst case running time of insertion sort is Ω($n^{2}$) " . Could anyone explain this line ?
asked
Jun 23, 2017
in
Algorithms
by
ashwina
Active
(
1.8k
points)

121
views
algorithms
asymptoticnotations
+1
vote
2
answers
6
Time complexity
what is time complexity for T(n) = √n.T(√n) + √n ?
asked
Jun 11, 2017
in
Algorithms
by
Saswat Senapati
(
253
points)

181
views
timecomplexity
asymptoticnotations
algorithms
0
votes
2
answers
7
Gate Sample Practise
Which of the following is not O(n^2)? (a) (15^10) * n + 12099 (b) n^1.98 (c) n^3 / (sqrt(n)) (d) (2^20) * n
asked
May 25, 2017
in
Algorithms
by
Pranav Madhani
Junior
(
745
points)

629
views
geekstogeeks
algorithms
asymptoticnotations
+1
vote
1
answer
8
Sample question for practise doubt
Consider the following 2 functions: f(n)= n3, if 0 ≤ n < 10,000 = n2, otherwise g(n)= n, if 0 ≤ n < 100 = n2 + 5n, otherwise Which of the following option is correct? (a) f(n) is O(n3) (b) g(n) is O(n3) (c) O(f(n)) is same as O(g(n)) (d) g(n) is O(1)
asked
May 25, 2017
in
Algorithms
by
Pranav Madhani
Junior
(
745
points)

702
views
asymptoticnotations
0
votes
1
answer
9
MadeEasy Subject Test: Algorithms  Asymptotic Notations
hello sir i have doubt in this question. T(n) >= 2T(n/2) + theta(n) option are: O(n log n) omega(n log n) theta (n log n) how we to select which sign i have to use omega ,big oh ,theta ??????
asked
May 11, 2017
in
Algorithms
by
aaru14
(
493
points)

122
views
madeeasytestseries
algorithms
asymptoticnotations
+3
votes
1
answer
10
Solve using Recursion Tree method when both parts are unequal
T(n) = T$(\frac{n}{3})$ + T$(\frac{2n}{3})$ + O(n)
asked
May 7, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.8k
points)

710
views
algorithms
timecomplexity
asymptoticnotations
recurrence
+1
vote
1
answer
11
Solve the Recurrence using Master Total Confusion as fraction part is there
T(n) =3T($n^{_{3}^{1}}$) + log 3n
asked
May 7, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.8k
points)

219
views
algorithms
timecomplexity
asymptoticnotations
recurrence
+2
votes
2
answers
12
Solve the Recurrence using Iteration Method
Solve the Recurrence using Iteration Method T(n)=3$(\frac{n}{4})$ + n
asked
May 7, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.8k
points)

330
views
algorithms
timecomplexity
asymptoticnotations
recurrence
+2
votes
2
answers
13
Doubt
How to get complexity of recurrence: $T(n) = \sqrt{n} .T(\sqrt{n}) + n$
asked
May 7, 2017
in
Algorithms
by
agoh
Active
(
1.7k
points)

184
views
recurrence
asymptoticnotations
+1
vote
2
answers
14
Cormen 3rd edition
Which is asymptotically larger: lg(lg* n) or lg* (lg n)?
asked
May 5, 2017
in
Algorithms
by
Injila
(
173
points)

556
views
algorithms
functions
asymptoticnotations
0
votes
0
answers
15
Complexity
We have for Counting Sort, O(n+k), for a simple uniform hashing, search operation of O(1+alpha) etc. What is the meaning when we say n + k? Is it that counting sort will depend on either n or k? Because there are separate loops in counting sort running on O(n) and O(k) separately. What does O(n + k) mean? What kind of algorithms have this summation for their order, generally?
asked
Apr 27, 2017
in
Algorithms
by
Ciado
(
205
points)

122
views
algorithms
timecomplexity
asymptoticnotations
sorting
+1
vote
1
answer
16
Peter Linz, 3rd Ed, Chapter 1, Pg 15, Ques 19
if f(n) = O(n2) and g(n) = O(n3), then what is the complexity of f(n)*g(n) and f(n)/g(n) in bigonotation?
asked
Apr 21, 2017
in
Theory of Computation
by
Vishal Goel
Active
(
1.8k
points)

93
views
theoryofcomputation
asymptoticnotations
+3
votes
4
answers
17
solve the recurrence using any method just solve it
T(n) = 100 T (n/99) + log(n!) Answer is T(n) = θ (n log n) a)answer is justified b)answer is not justified c)cannot be determined d)none
asked
Apr 17, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.8k
points)

502
views
algorithms
timecomplexity
asymptoticnotations
recurrence
+1
vote
1
answer
18
#BigO#Rosen
Give BigO estimate: ${f(x)=n^{2n} + n^{n^2}}$ The answer is given $O(n^{2n})$ But, isn't $n^{n^2} > n^{2n}$ for n>2? If yes, then how is it $O(n^{2n})$?
asked
Apr 7, 2017
in
Set Theory & Algebra
by
codinion
(
57
points)

170
views
timecomplexity
asymptoticnotations
0
votes
3
answers
19
Solve the following Recurrence using any method
T(n) = 2n T $(\frac{n}{2})$ + nn
asked
Mar 27, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.8k
points)

305
views
algorithms
timecomplexity
asymptoticnotations
recurrence
+1
vote
1
answer
20
Solve the following recurrence using any method
T(n)=T $(\frac{n}{2})$ + T $(\frac{n}{4})$ + n2
asked
Mar 27, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.8k
points)

149
views
algorithms
timecomplexity
asymptoticnotations
recurrence
0
votes
3
answers
21
Asymptotic notations
Is $ (5  n^3) \in \Omega (n^2) $ ?
asked
Mar 17, 2017
in
Algorithms
by
ku060996
(
27
points)

200
views
asymptoticnotations
+32
votes
9
answers
22
GATE2017104
Consider the following functions from positive integers to real numbers: $10$, $\sqrt{n}$, $n$, $\log_{2}n$, $\frac{100}{n}$. The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is: $\log_{2}n$, $\frac{100}{n}$, $10$, $\sqrt{n}$, $n$ $\frac{100}{n}$, ... $\sqrt{n}$, $\log_{2}n$, $n$ $\frac{100}{n}$, $\log_{2}n$, $10$, $\sqrt{n}$, $n$
asked
Feb 14, 2017
in
Algorithms
by
khushtak
Loyal
(
7.1k
points)

4.3k
views
gate20171
algorithms
asymptoticnotations
normal
+2
votes
1
answer
23
Gatebook_Mocktest2(DS)
The intended purpose of this code is to precompute all the primes less than N. When it is finished executing, for r ∈ [2, N), bits[r] is supposed to equal 1 if and only if N is composite. Assume that the bits array is initialized to all zeroes. for ( int x = 2; x < N ... a natural number n < N is prime. (A) I only (B) I and II only (C) II and III only (D) I, II, and III
asked
Feb 8, 2017
in
DS
by
smartmeet
Active
(
4.9k
points)

222
views
gatebook_mt2
datastructures
spacecomplexity
timecomplexity
asymptoticnotations
+1
vote
1
answer
24
how to solve this recurrence using Recursion Tree method
T(n) = T(n1) + n4
asked
Feb 4, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.8k
points)

241
views
algorithms
timecomplexity
asymptoticnotations
recurrence
+2
votes
0
answers
25
ASYMPTOTIC GROWTH
Consider the case: f(n) = O(g(n)). Then, following two statements are claimed to be inferred from the above case. Statement I: 2f(n) = O(2g(n)) Statement II: 2g(n) = O(2f(n)) Choose the correct option from the given. Both correct. Both incorrect S1 correct, S2 false S2 false,S1 correct
asked
Feb 4, 2017
in
Algorithms
by
sushmita
Boss
(
17.7k
points)

165
views
timecomplexity
asymptoticnotations
growthrate
algorithms
0
votes
1
answer
26
How to solve this Recurrence using Iteration method
T(n) = 3 T $(\frac{n}{4})$ + n
asked
Feb 3, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.8k
points)

233
views
algorithms
timecomplexity
asymptoticnotations
recurrence
+1
vote
1
answer
27
Solve the Following Recurrence using Iteration Method
T(n) = 4T $(\frac{n}{3})$ + n2
asked
Feb 3, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.8k
points)

159
views
algorithms
timecomplexity
asymptoticnotations
recurrence
+4
votes
1
answer
28
Finding time complexity of series
asked
Feb 3, 2017
in
Algorithms
by
GateAspirant999
Active
(
2.5k
points)

255
views
timecomplexity
algorithms
asymptoticnotations
0
votes
2
answers
29
Operation on a function and its big O
asked
Feb 3, 2017
in
Algorithms
by
GateAspirant999
Active
(
2.5k
points)

108
views
asymptoticnotations
algorithms
timecomplexity
0
votes
1
answer
30
Solve the recurrence using Recursion Tree method
T(n) = T(n1) + n4
asked
Feb 2, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.8k
points)

343
views
algorithms
timecomplexity
asymptoticnotations
recurrence
Page:
« prev
1
2
3
4
5
6
7
8
9
10
11
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 asymptoticnotations
Recent Blog Comments
Cut off will be between 95115 not more than that.
@saxena0612 , Sir since they are not considering...
Hey Everyone! Those who think that they are...
Which questions are u challenging..?
ONLY T MADE EASY STUDENTS CAN UNDERSTAND,
50,737
questions
57,370
answers
198,506
comments
105,272
users