The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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 asymptoticnotations
Notations
0
votes
0
answers
1
Time Complexity
I am unable to Find its time complexity using Iterative method… Will any one help me out with this . Thank you :)
asked
Jan 18
in
Algorithms
by
Nandkishor3939
Active
(
1.2k
points)

62
views
timecomplexity
algorithms
asymptoticnotations
0
votes
0
answers
2
Algorithm analysis
Find a growth rate that cubes the run time when we double the input size. That is, if T(n) = X, then T(2n) = x^3.
asked
Jan 13
in
Algorithms
by
debanjan sarkar
Active
(
4.1k
points)

21
views
asymptoticnotations
algorithms
0
votes
0
answers
3
Asymptotic notation
Let f(n) =O(n), g(n)=Ώ(n) and h(n)=Θ(n). Then g(n)+f(n).h(n) is _____? a Ω($n^{2}$) b Θ($n^{2}$) cΩ(n) dΘ(n)
asked
Jan 12
in
Algorithms
by
bts1jimin
(
245
points)

43
views
asymptoticnotations
algorithms
timecomplexity
0
votes
0
answers
4
Algorithms Time complexity
asked
Jan 12
in
Programming
by
Rackson
Active
(
1.8k
points)

42
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
5
made easy test
Given below are 4 functions $999999n$ $0.99999 n logn$ $1.000001^{n}$ $n^{2}$ The increasing order of the above functions in terms of their asymptotic complexity is?
asked
Jan 10
in
Algorithms
by
snaily16
(
255
points)

32
views
algorithms
asymptoticnotations
0
votes
0
answers
6
Time Complexity Analysis  Madeeasy 2019
Please show the ideal way to deal with such comparisons as I am getting g>=f IN genral what logic shall be followed to analyse such complex comparions?
asked
Jan 6
in
Algorithms
by
Markzuck
Junior
(
635
points)

33
views
algorithms
asymptoticnotations
madeeasytestseries
0
votes
0
answers
7
Time complexity (Advance Level)
The difference of time Complexity between given functions can be represented by: void fun1(int n) { for(int i=1;i<=n;i++) for(int j=1;j<=i*i;j++) if(j%i==0) for(int k=1;k<=j;k++) s++; return 0; } void fun2(int n) { for(int i=1;i<=n;i++) for(int j=1;j<=i*i;j++) for(int k=1;k<=j;k++) s++; return 0; } $i. O(n^2)$ $ii. O(n)$ $iii.O(1)$ $iv. O(n^{1.5})$
asked
Jan 4
in
Algorithms
by
shreyansh jain
Active
(
2.1k
points)

69
views
timecomplexity
asymptoticnotations
algorithms
0
votes
0
answers
8
#algorithm
Write the BigO notation for the following functions. Mention if they are exponential, polynomial, logarithmic or neither of those. Proof is not required, but write one or two sentences about how you arrived at the answer. (a) n log n + .01n$^{3/2}$ + 10n (b) log n!/n (c) 1.01$^{n}$ + n3 (d) .99$^{n}$ + n (e) log(n + n – 1 + ……..+ 1) (f) n.$^{.01}$ + log n2
asked
Jan 4
in
Algorithms
by
amit166
Junior
(
693
points)

18
views
big
asymptoticnotations
0
votes
1
answer
9
Time Complexity of Code snippet
What will be the worst case time complexity for the following code segment? int count=0,N; for(i=0;i<N*2;i++){ for(j=0;j<i/3;i++){ for(k=0;k<j*j;k++){ count++; } } } Options: O(N^4) O(N^3) O(N^2) O(N)
asked
Jan 4
in
Algorithms
by
saptarshiDey
(
83
points)

81
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
10
time complexity
asked
Dec 30, 2018
in
Algorithms
by
Rahul_Rathod_
Junior
(
565
points)

28
views
timecomplexity
algorithms
asymptoticnotations
recurrence
0
votes
0
answers
11
Madeeasy  Time complexity 2019
cant we write the recurrance relation for bar() as T(n) = 5T(n1) + c, like cant we take both the recurrance call as combined as both have same parameter? and if not, then how to solve such?
asked
Dec 29, 2018
in
Algorithms
by
Markzuck
Junior
(
635
points)

59
views
timecomplexity
algorithms
madeeasytestseries
asymptoticnotations
+3
votes
1
answer
12
GO2019FLT148
Consider the following piece of pseudocode: A(n){ if(n==0) return 1; return A(√n) + B(n) + C(n) + D(n); } B(n){ if (n==0) return n; return B(n1); } C(n){ return A (√n); } D(n){ return n; } What is the time complexity in terms of Big $\Theta$ notation for the function call to procedure A? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n \log \log n)$ $\Theta(n^2 \log n)$
asked
Dec 27, 2018
in
Others
by
Ruturaj Mohanty
Active
(
2.9k
points)

237
views
go2019flt1
asymptoticnotations
recurrence
+1
vote
0
answers
13
Self Doubt
Kindly verify these and provide answer to others $\\\Theta (n).O(n) = ?\\ \Theta (n).\Omega (n) = \Omega (n)\\ O(n).\Omega (n) = \Omega (n)\text{when function is non decreasing and what if it is decreasing?}\\ \Omega (n)+\Theta (n) =\Omega (n)\\ O(n)+\Theta (n) = ?\\ O(n)+\Omega (n)=\Theta (n)$
asked
Dec 27, 2018
in
Algorithms
by
Shubhgupta
Loyal
(
8.4k
points)

71
views
asymptoticnotations
0
votes
1
answer
14
#timecomplexity
What is difference between tightest upper bound and tightest lower bound? Give ur explanation with examples?
asked
Dec 26, 2018
in
Algorithms
by
Deepesh Pai
(
499
points)

23
views
timecomplexity
algorithms
asymptoticnotations
0
votes
0
answers
15
Highest best case implies worst case?
Which of the below given sorting techniques has highest bestcase runtime complexity. (A) Quick sort (B) Selection sort (C) Insertion sort (D) Bubble sort Answer: (B) Explanation: Quick sort best case time complexity is Ο(n logn) Selection sort ... 12/ I did not understand this as best case time should be O(n) sorting method what does highest best cases mean?
asked
Dec 23, 2018
in
Algorithms
by
sripo
Active
(
1.5k
points)

49
views
algorithms
asymptoticnotations
datastructure
sorting
timecomplexity
0
votes
0
answers
16
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
Dec 11, 2018
in
Algorithms
by
Shivam Kasat
Active
(
1.9k
points)

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

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

67
views
timecomplexity
asymptoticnotations
recurrence
algorithms
+4
votes
0
answers
19
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, 2018
in
Algorithms
by
Ayush Upadhyaya
Boss
(
24.4k
points)

68
views
asymptoticnotations
algorithms
0
votes
1
answer
20
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, 2018
in
Algorithms
by
Shubham Aggarwal
Active
(
1.9k
points)

131
views
asymptoticnotations
recurrence
0
votes
0
answers
21
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, 2018
in
Algorithms
by
sripo
Active
(
1.5k
points)

77
views
algorithms
timecomplexity
asymptoticnotations
spacecomplexity
+1
vote
1
answer
22
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, 2018
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
29k
points)

41
views
algorithms
asymptoticnotations
growthrate
+1
vote
1
answer
23
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, 2018
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
29k
points)

61
views
algorithms
asymptoticnotations
timecomplexity
growthrate
0
votes
0
answers
24
asymptotic notations
√logx = O(loglogx) is it true or false? and explain why?
asked
Oct 29, 2018
in
Algorithms
by
suneetha
Junior
(
553
points)

35
views
asymptoticnotations
+1
vote
1
answer
25
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, 2018
in
Algorithms
by
aditi19
Active
(
2.3k
points)

92
views
timecomplexity
algorithms
asymptoticnotations
recurrence
+2
votes
1
answer
26
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, 2018
in
Algorithms
by
chauhansunil20th
Active
(
4.8k
points)

193
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
27
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, 2018
in
Algorithms
by
Verma Ashish
Active
(
4.7k
points)

35
views
asymptoticnotations
0
votes
1
answer
28
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, 2018
in
Algorithms
by
sushmita
Boss
(
16.8k
points)

85
views
timecomplexity
algorithms
asymptoticnotations
Page:
1
2
3
4
5
6
...
10
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
Relax... But....
Barc : Arjun Sir
JEST Sample Question
Manipal institute of technology , Vellore Institute of technology, BARC, Interview M.Tech
What to do and scared for future
Follow @csegate
Recent questions tagged asymptoticnotations
Recent Blog Comments
send me also
[email protected]
ok done
or u can upload the pdf file on google drive...
send me at
[email protected]
Do IITB/IISc also have winter admissions?
47,894
questions
52,260
answers
182,165
comments
67,679
users