The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google 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 asymptoticnotations
Notations
0
votes
0
answers
1
Question_bank
f(n)=O(g(n)) Which of the following is True? 2^f(n)=O(2^(g(n)) log(f(n))=O(log(g(n)) f(n)=O(f(n/2)) f(n)=O(f(n)^2)
asked
4 days
ago
in
Algorithms
by
Shivam Kasat
Junior
(
803
points)

20
views
algorithms
timecomplexity
asymptoticnotations
0
votes
1
answer
2
selfas
f(n) + O(f(n)) = Θ(f(n)) True or not? Explain please
asked
Nov 18
in
Algorithms
by
Vegeta
Junior
(
567
points)

27
views
algorithms
asymptoticnotations
0
votes
0
answers
3
Time Complexity
How to solve the following recurrence relation? T(n) = T(n6) + n2 , n>7 T(n) = 1 , n<= 7
asked
Nov 17
in
Algorithms
by
garvit_vijai
(
149
points)

47
views
timecomplexity
asymptoticnotations
recurrence
algorithms
+4
votes
0
answers
4
GATEBOOK_DS_1_12_Asymptotic_Notations
Which of the following is the correct order if they are ordered by asymptotic growth rates? $F_1:n^{lg\,lgn}$ $F_2:(3/2)^n$ $F_3:(lg\,n)^{lg\, n}$ $F_4:n!$ $F_3$ can be rewritten as $n^{lg\,lgn}$ using property $a^{log_bc}=c^{log_ba}$ So, $F_4 \gt F_2 \gt F_1=F_3$ Is my order correct?
asked
Nov 14
in
Algorithms
by
Ayush Upadhyaya
Boss
(
18.8k
points)

67
views
asymptoticnotations
algorithms
0
votes
1
answer
5
test series  Testbook
Which of the following functions given by their recurrences grows the fastest asymptotically? $T(n) = 8T(n/4) + 100n^2$ $T(n) = 81T(n/9) + 10n^2$ $T(n) = 16T(n/4)+ 100(n \log n)^{1.99}$ $T(n) = 100T(n/100)+ n \log^2 n$
asked
Nov 13
in
Algorithms
by
Shubham Aggarwal
Active
(
1.4k
points)

121
views
asymptoticnotations
recurrence
0
votes
0
answers
6
Time Complexity for an infinite loop
What is the time complexity for infinite loops Question 1 what is T(n) for this case While(1) { a=a+b; } Question 2 for this case if(1) { for i to n a=a+b } else { for i to n for j to n a=a+b } Edit 2: Compiled the code ... ); return 0; } output I get is 8 6 which means the else case is never executed hence in worst case do we have to consider the else part.
asked
Nov 6
in
Algorithms
by
sripo
Junior
(
931
points)

47
views
algorithms
timecomplexity
asymptoticnotations
spacecomplexity
+1
vote
1
answer
7
Asymptotic Notations with condition
Identify the FALSE statement: $A)$ $f(n)=\theta(f(\frac{n}{2})$ $implies$ $f(n^{2})=\theta(f(\frac{n^{2}}{2}))$ $B)$ $f(n)=O(g(n))$ $implies$ $log(f(n))=O(log(g(n)))$ where $n\geq2$ $C)$ $f(n)=O(g(n))$ $implies$ $2^{f(n)}=O(2^{g(n)})$ $D)$ $f(n)+g(n)=\theta(Max(f(n),g(n)))$
asked
Nov 1
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
19.5k
points)

29
views
algorithms
asymptoticnotations
growthrate
+1
vote
1
answer
8
Asymptotic Notations
Consider the following statements: $(1)$ Any two functions $f,g$ are always comparable under big Oh,that is $f=O(g)$ or $g=O(f)$ $(2)$ If $f=O(g)$ and $f=O(h)$ then $g(n)=\theta(h)$ $A)$ $(1)$ is true $(2)$ is false $B)$ $(1)$ is false $(2)$ is true $C)$ Both are false $D)$ Both are true
asked
Nov 1
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
19.5k
points)

44
views
algorithms
asymptoticnotations
timecomplexity
growthrate
0
votes
0
answers
9
asymptotic notations
√logx = O(loglogx) is it true or false? and explain why?
asked
Oct 29
in
Algorithms
by
suneetha
(
379
points)

32
views
asymptoticnotations
+1
vote
1
answer
10
Time Complexity
how to compute time complexity of this kind of recurrence relation T(n)=T(n/2)+T(n/4)+T(n/8)+n
asked
Oct 27
in
Algorithms
by
aditi19
Active
(
2.1k
points)

71
views
timecomplexity
algorithms
asymptoticnotations
recurrence
+2
votes
0
answers
11
Algorthms: time Complexity
If $f(n) =O(n),g(n)=\Omega(\sqrt[3]{n}), and, h(n)=o(n^3), then, f(g(n)) = O(\sqrt{h(n)})$ Is this true or false?
asked
Oct 19
in
Algorithms
by
chauhansunil20th
Active
(
1.8k
points)

183
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
12
Asymptotic notations
Consider the following statements: S1: f(n) = O(f(n)²) S2: If f(n) = O(g(n)) then ${2^{f(n)}}$ = O(${2^{g(n)}}$) S3: If f(n) = O(g(n)) and h(n) = Ɵ(g(n)) then f(n)•h(n) = O(g(n)•h(n)) Which of the statements are correct?? (A) only S2 (B) only S3 (C) both S1 and S2 (D) both S2 and S3.
asked
Oct 3
in
Algorithms
by
Verma Ashish
Active
(
2.7k
points)

30
views
asymptoticnotations
0
votes
1
answer
13
time complexity
If both of the algorithms A and B need O(nlogn) time then they both are equally efficient and finish in same amount of time. TRUE OR FALSE
asked
Sep 28
in
Algorithms
by
sushmita
Boss
(
15.3k
points)

83
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
14
MIT assignment
Find the complexity of the following code fragment: int i = 1; for(; i <= n logn; i + +) { for(i + +; i <= n; i + +) { print(1) } }
asked
Sep 28
in
Algorithms
by
sushmita
Boss
(
15.3k
points)

99
views
timecomplexity
asymptoticnotations
algorithms
0
votes
3
answers
15
Can we solve the recurrence T(n) = T(n/2) + 2^n by masters theorem, if possible?
asked
Sep 28
in
Algorithms
by
mohitrai0_0
(
247
points)

123
views
recurrence
algorithms
mastertheorem
timecomplexity
asymptoticnotations
+1
vote
2
answers
16
MIT ASSIGNMENT
Find the complexity of the following function when called with some integer n: void foo(n) { int i,j,k,x=0; for (i=1 ; i ≤ n ; i++) for (j=1 ; j ≤ i * i ; j++) { for ( k = 1 ; k ≤ j ; k++) { x=x+10; } }
asked
Sep 28
in
Algorithms
by
sushmita
Boss
(
15.3k
points)

123
views
algorithms
timecomplexity
asymptoticnotations
0
votes
2
answers
17
MIT ASSIGNMENT
FIND THE TIME COMPLEXITY int i=1,j; for(;i <= n;i + +) { for(j = i; j <= nlogn; j∗ = 2) { sum + +; } }
asked
Sep 28
in
Algorithms
by
sushmita
Boss
(
15.3k
points)

90
views
algorithms
timecomplexity
asymptoticnotations
0
votes
1
answer
18
MIT assigment
Arrange the following functions in their increasing order of complexities. $f(n) = n ^{0.999999} * logn$ ($log n$ is not in power) $g(n) = 10000 n$ $h(n) = n^{2}$ $k(n) = (1.000001)^{n}$ $p(n) =\large \frac{2 ^{√n}}{ n^{2}}$ $q(n) = \Large \frac{n^{1.000001}}{logn}$
asked
Sep 28
in
Algorithms
by
sushmita
Boss
(
15.3k
points)

170
views
timecomplexity
algorithms
asymptoticnotations
0
votes
0
answers
19
mit assignment
State true/false f(n) != O(g(n)) and g(n) != O(f(n))
asked
Sep 28
in
Algorithms
by
sushmita
Boss
(
15.3k
points)

41
views
algorithms
timecomplexity
asymptoticnotations
0
votes
0
answers
20
Cormen Appendix A
Why does (1/3+1/c) <=1?
asked
Sep 22
in
Algorithms
by
Noddy
(
27
points)

15
views
algorithms
asymptoticnotations
timecomplexity
0
votes
1
answer
21
Asymptoticnotations
f(n)=2(log2 n)2 , g(n)=log2n+1 How to give relation between them?.
asked
Sep 22
in
Algorithms
by
Vishnathan
(
341
points)

45
views
timecomplexity
asymptoticnotations
0
votes
1
answer
22
timecomplexcity
for(i=0;i<n;i++) for(j=0;j<i;j++) for(k=0;k<j;k++) what is the time complexity of above psudo code? explain.
asked
Sep 21
in
Algorithms
by
balaganesh
(
129
points)

47
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
23
Algorithms Complexity
asked
Sep 21
in
Algorithms
by
Vaishnavi01
(
215
points)

98
views
algorithms
timecomplexity
asymptoticnotations
0
votes
1
answer
24
Time complexity of code given
asked
Sep 17
in
Algorithms
by
GateAspirant999
Active
(
2.8k
points)

66
views
#time
timecomplexity
asymptoticnotations
0
votes
0
answers
25
Time Complexity
Please help with the following in Time Complexity. 1)Show that the following orderofmagnitude results hold: a)3n=O(n!) b)(n3 2n)/(n+1)=theta(n2) c)n3 /log(n+1)=O(n3) but not O(n2) 2)What is wrong with the following argument? x=O(n4),y=O(n2),therefore x/y=O(n2). 3) What is ... the following argument? f(n)=O(n2)+O(n), so that f(n)g(n)=O(n2 )+O(n)O(n2). Therefore, f(n)g(n)=O(n)
asked
Sep 10
in
Algorithms
by
Devshree Dubey
Boss
(
13.6k
points)

45
views
timecomplexity
algorithms
asymptoticnotations
0
votes
0
answers
26
time complexcity
Following algorithms can be used to sort n integers in range [1...n^3] in O(n) time? a)Heap sort b)Quick sort c)Merge sort d)Radix sort
asked
Sep 7
in
Algorithms
by
balaganesh
(
129
points)

24
views
time
timecomplexity
algorithms
asymptoticnotations
0
votes
0
answers
27
Algorithm
How is Σ (1/k * log k) = O( n log n) for k=1 to n?
asked
Sep 7
in
Algorithms
by
Nidhi Budhraja
(
203
points)

30
views
algorithms
timecomplexity
asymptoticnotations
0
votes
2
answers
28
alagorithms analysis
The running time of an algorithm is given by T(n)=T(n1)+T(n2)T(n3), ifn>3 =n, otherwise The order of this algorithm is a)n b)log n c)n^n d)n^2 explain !
asked
Sep 5
in
Algorithms
by
balaganesh
(
129
points)

57
views
algorithms
asymptoticnotations
0
votes
0
answers
29
time complexity
I got this question from here https://gateoverflow.in/169286/timecomplexity Is this Question Correct i have doubt . If correct please explain Which of the following statements is/are TRUE? $i)$ The time complexity of recurrence relation $A(n) = 3A(n/2)+n^{2} $is ... $O( 7 ^ {n/53})$ is asymptotically faster But i am not able to get the answer because of question statement .
asked
Aug 22
in
Algorithms
by
Rishav Kumar Singh
Active
(
4.6k
points)

84
views
timecomplexity
asymptoticnotations
recurrence
0
votes
1
answer
30
Time Complexity
What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list? a) O(1) b) O(n) c) θ(n) d) θ(1)
asked
Aug 19
in
Programming
by
pradeepchaudhary
Junior
(
919
points)

32
views
asymptoticnotations
datastructure
Page:
1
2
3
4
5
6
...
9
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
IIT HYDERABAD M.Tech (RA) 3Years Winter Session Interview experience
INDIAN AIR FORCE
GATE BOOK _ TEST SERIES DOUBT_
Visualizing complex C code
GATE Book Test Series
Follow @csegate
Gatecse
Recent questions tagged asymptoticnotations
Recent Blog Comments
There is one more problem. Ppl who have...
CL013924707IN rt?
I ordered the GO BOOK 6 dec ....but still i didnt...
thankyou sir
44,240
questions
49,722
answers
163,928
comments
65,837
users