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
+1
vote
1
answer
1
Self doubt
Consider the following functions
asked
Jun 28, 2018
in
Algorithms
by
Doley
(
129
points)

40
views
asymptoticnotations
0
votes
1
answer
2
what is the tightest bound for the below functions ?
n2 + O(n2) = Theta(n2) I am not getting how can we say that tightest bound is in terms of theta , because theta(n2 ) implicitly implies BigOmega(n2 ) and Big O(n2 ) , Now If we say the function f(n) is BigOmega(n2 ... will never get a function greater than n2 so how can we say the tightest bound to be BigOmega(n2 ) ? Please explain briefly .
asked
Jun 24, 2018
in
Algorithms
by
radha gogia
Loyal
(
6.3k
points)

130
views
algorithms
asymptoticnotations
0
votes
0
answers
3
Asymptotic Complexity
$T\left ( n,c \right )=\Theta \left ( n \right )$ for $c\leq 2$ $T\left ( c,n \right )=\Theta \left ( n \right )$ for $c\leq 2$ $T\left ( n,n \right )=\Theta \left ( n \right )+T\left ( n,\frac{n}{2} \right )$ How to find complexity for this recurrence relation?
asked
Jun 22, 2018
in
Algorithms
by
srestha
Veteran
(
117k
points)

107
views
algorithms
timecomplexity
asymptoticnotations
+1
vote
0
answers
4
Time Complexity
What will be the time complexity of the following algorithm ? A(n){ if(n<=1) return 1; for(i=1;i<n;i++){ for(j=0;j<3;j++){ A(n1) } } }
asked
Jun 17, 2018
in
Algorithms
by
kartikeya2812
(
21
points)

117
views
timecomplexity
algorithms
asymptoticnotations
recursion
+2
votes
1
answer
5
Extended Master's Theorem $T(n)=n^{1/2}T(n^{1/2})+n$
Can Extended Masters theorem be applied to the following recursive equation ? $T(n)=n^{1/2}T(n^{1/2})+n$ I solved this using back substitution and the time complexity came out to be $O(n*(loglogn))$ I was wondering if this ... masters theorem, like the way Tauhin Gangwar has solved here  https://gateoverflow.in/60532/findtctn2tn121
asked
Jun 11, 2018
in
Algorithms
by
Hardik Maheshwari
(
93
points)

413
views
timecomplexity
algorithms
mastertheorem
asymptoticnotations
recurrence
0
votes
0
answers
6
Cormen 3rd edition Problem 32 part (f)
Indicate for pair of expressions (A,B) whether A is O, o, Ω, ω or of B? A = lg(n!) B = lg(n^n)
asked
Jun 11, 2018
in
Algorithms
by
Aarvi Chawla
(
365
points)

37
views
asymptoticnotations
+1
vote
2
answers
7
Cormen
T(n)=T(n1)+2n where T(1)=1 Solve recurrence relation
asked
Jun 8, 2018
in
Algorithms
by
vijju532
Active
(
1k
points)

126
views
recurrenceeqation
algorithms
asymptoticnotations
timecomplexity
0
votes
0
answers
8
Complexity
#DAA Prove that if: f(n) = amnm + am1nm1 + am2nm2 + am3nm3 + .........+ a1n + a0 then f(n) = O(nm) .
asked
Jun 6, 2018
in
Algorithms
by
Naveen Kumar 3
Boss
(
15.2k
points)

45
views
algorithms
timecomplexity
asymptoticnotations
+1
vote
2
answers
9
Analysis of algorit
Which of the following statements is/are valid? 1. Time Complexity of QuickSort is Θ(n^2) 2. Time Complexity of QuickSort is O(n^2) 3. For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). 4. Time complexity of all computer algorithms can be written as Ω(1)
asked
Jun 6, 2018
in
Algorithms
by
jatinkumar
(
307
points)

299
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
10
Big O
asked
May 10, 2018
in
Algorithms
by
Sanjay Sharma
Boss
(
48.8k
points)

103
views
asymptoticnotations
timecomplexity
0
votes
1
answer
11
Cormen 3rd edition Exercise 4.4.9
Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) =T(an)+T((1a)n)+cn, where a is constant in the range 0<a<1 and c>0 is also a constant.
asked
Apr 27, 2018
in
Algorithms
by
Neha_16
(
285
points)

115
views
algorithms
asymptoticnotations
0
votes
1
answer
12
Asymtotic notation
Big Omega question : 5n+3>=C2n for which value of c and n condition satisfies?
asked
Apr 17, 2018
in
Algorithms
by
once_2019
Junior
(
643
points)

49
views
asymptoticnotations
0
votes
1
answer
13
Zeal Indore
Compute: T(n) = 2^nT(n/2) +n^n 1)theta(n^n) 2)theta(nlogn) 3)theta(n^nlogn) 4)none of these.
asked
Apr 15, 2018
in
Algorithms
by
Harshit Pandey
(
25
points)

148
views
algorithms

asymptoticnotations
0
votes
1
answer
14
time complexity
asked
Apr 11, 2018
in
Algorithms
by
Beyonder
(
499
points)

108
views
timecomplexity
algorithms
asymptoticnotations
programminginc
+2
votes
2
answers
15
Algorithms time Complexity
What is the time complexity of this code?
asked
Apr 5, 2018
in
Algorithms
by
gauravkc
Loyal
(
7.8k
points)

195
views
timecomplexity
algorithms
asymptoticnotations
0
votes
0
answers
16
Recurrence
When T(n) = a T(n/b) + f(n) If on solving we get g(n) as upper bound solution for the recurrence. Is f(n) = O( g(n) ) always correct?
asked
Apr 3, 2018
in
Algorithms
by
smsubham
Loyal
(
9.8k
points)

120
views
recurrence
timecomplexity
algorithms
asymptoticnotations
+1
vote
1
answer
17
Cormen 4.3.8
Find the solution of recurrence $T(n) = 4T(\frac{n}{2}) + n^{2}$ by substitution method.
asked
Apr 2, 2018
in
Algorithms
by
Mk Utkarsh
Boss
(
35.7k
points)

141
views
asymptoticnotations
algorithms
+2
votes
1
answer
18
Cormen 4.45
Use the recursion tree to determine a good asymptotic upper bound on the recurrence T(n)=T(n1)+T($\frac{n}{2}$)+n. Use substitution method to verify the answer.
asked
Mar 9, 2018
in
Algorithms
by
Tesla!
Boss
(
18.3k
points)

238
views
algorithms
asymptoticnotations
recurrenceeqation
timecomplexity
+1
vote
1
answer
19
Introduction to Algorithm 36
For a given constant c $\in \mathbb{R}$, we define the iterated function $f_{c}^{*}$ by $f_{c}^{*}$(n)=min{${i\geq 0: f^{(i)}(n)<c}$} For each of the following function f(n) and constants c, give as tight a bound as possible on $f_{c}^{*}$ f(n) c $f_{c}^{*}$(n) $\sqrt{n}$ 2 $\sqrt{n}$ 1 n/lg n 2
asked
Mar 7, 2018
in
Algorithms
by
Tesla!
Boss
(
18.3k
points)

83
views
algorithms
asymptoticnotations
+1
vote
2
answers
20
Doubt in Asymptotic Analysis
Find theta bound for f(n)=$n^2/2 n/2$
asked
Mar 6, 2018
in
Algorithms
by
Devshree Dubey
Boss
(
13.7k
points)

116
views
algorithms
asymptoticnotations
+2
votes
1
answer
21
Equivalent Complexity
Given f(n) = ω(n2). Which of the following can never hold? a. f(n) = O (n3) b. f(n) = Ω (n2) c. f(n) = θ (n2) d. f(n) = ω (n)
asked
Jan 30, 2018
in
Algorithms
by
Tuhin Dutta
Loyal
(
9.8k
points)

83
views
algorithms
asymptoticnotations
timecomplexity
+2
votes
1
answer
22
Algorithms:Asymptotic Notations
plz help me . how to solve that type of question
asked
Jan 27, 2018
in
Algorithms
by
92komal
(
369
points)

82
views
algorithms
asymptoticnotations
+3
votes
1
answer
23
time complexity
time complexity questions like : h(n)=O(n2); f(n)= O(logn); g(n)=omega(n2); what is the complexity of :::: 1. h(n)g(n)=?? 2. h(n)f(n)=??? elaborate plz
asked
Jan 22, 2018
in
Algorithms
by
akankshadewangan24
Active
(
4k
points)

131
views
timecomplexity
asymptoticnotations
+2
votes
0
answers
24
MadeEasy Test Series 2018: Algorithms  Asymptotic Notations
Let f (n) = Ο(n), g(n) = Ω(n) and h(n) = θ(n). Then g(n) + f(n).h(n) is ______ A.) Ω(n) B.) θ(n2) C.) Ω(n2) D.) θ(n) How to do these type of questions ?
asked
Jan 22, 2018
in
Algorithms
by
ashish pal
Junior
(
823
points)

148
views
madeeasytestseries
algorithms
asymptoticnotations
+2
votes
1
answer
25
Asymptotic Notation
Given h(n) < f(n) < g(n). statement 1: h(n)=O(f(n)); g(n)=Ω(f(n)) Statement 1 is True / False?
asked
Jan 21, 2018
in
Algorithms
by
hacker16
Active
(
2.7k
points)

215
views
asymptoticnotations
algorithms
timecomplexity
growthrate
+3
votes
1
answer
26
time complexity
asked
Jan 16, 2018
in
Algorithms
by
pranab ray
Junior
(
779
points)

138
views
timecomplexity
algorithms
asymptoticnotations
0
votes
3
answers
27
time complexity
i am getting t.c as O(n^5) but given answer as O(n^4) what should be the answer
asked
Jan 13, 2018
in
Algorithms
by
pranab ray
Junior
(
779
points)

102
views
timecomplexity
algorithms
asymptoticnotations
+3
votes
1
answer
28
recurrence eq
how to solve this T(n)=T(n−1)+T(n−2) if T(0)=T(1)=1
asked
Jan 12, 2018
in
Algorithms
by
iarnav
Loyal
(
8.3k
points)

130
views
recurrence
algorithms
timecomplexity
asymptoticnotations
discretemathematics
0
votes
0
answers
29
divide and conquer
in questions like how many multiplications of n are needed are being solved by dividing n into n/2 * n/2 and then end up with recurrence t(n) = t(n/2) + O(1) How to reach this type of analysis where we get to know that we have to divide n into halves?
asked
Jan 12, 2018
in
Algorithms
by
iarnav
Loyal
(
8.3k
points)

136
views
divideandconquer
algorithms
asymptoticnotations
+2
votes
1
answer
30
recurrence using Master theorem
can we solve this T(n) = T(n/2) + 1 using master theorem?
asked
Jan 11, 2018
in
Algorithms
by
iarnav
Loyal
(
8.3k
points)

254
views
algorithms
mastertheorem
timecomplexity
recurrence
asymptoticnotations
Page:
« prev
1
2
3
4
5
6
7
8
9
...
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
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged asymptoticnotations
Recent Blog Comments
Amazing work Sir
Not in my hands. Flipkart is showing my location...
Arjun sir, plz provide go book through...
@
[email protected]
Can this be updated?
Even In 2019 my 16 questions goes for negative...
50,644
questions
56,505
answers
195,555
comments
101,042
users