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
0
votes
1
answer
1
Algorithms Time complexity
asked
Jan 12, 2019
in
Programming
by
Rackson
Active
(
1.8k
points)

78
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
2
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, 2019
in
Algorithms
by
snaily16
(
245
points)

55
views
algorithms
asymptoticnotations
0
votes
0
answers
3
MadeEasy Test Series: Algorithms  Time Complexity
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, 2019
in
Algorithms
by
Markzuck
Junior
(
675
points)

94
views
algorithms
asymptoticnotations
madeeasytestseries
timecomplexity
0
votes
0
answers
4
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, 2019
in
Algorithms
by
shreyansh jain
Active
(
2.2k
points)

134
views
timecomplexity
asymptoticnotations
algorithms
0
votes
0
answers
5
#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) $\frac{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, 2019
in
Algorithms
by
amit166
Junior
(
775
points)

35
views
asymptoticnotations
0
votes
1
answer
6
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, 2019
in
Algorithms
by
saptarshiDey
(
117
points)

285
views
timecomplexity
algorithms
asymptoticnotations
0
votes
0
answers
7
MadeEasy Test Series 2019: Algorithms  Time complexity
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
(
675
points)

141
views
timecomplexity
algorithms
madeeasytestseries
asymptoticnotations
+4
votes
1
answer
8
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
Algorithms
by
Ruturaj Mohanty
Active
(
2.7k
points)

299
views
go2019flt1
asymptoticnotations
recurrence
algorithms
+1
vote
0
answers
9
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
(
9.2k
points)

85
views
asymptoticnotations
0
votes
1
answer
10
#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
(
411
points)

40
views
timecomplexity
algorithms
asymptoticnotations
0
votes
0
answers
11
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
(
2.4k
points)

111
views
algorithms
asymptoticnotations
datastructures
sorting
timecomplexity
0
votes
2
answers
12
TIFR2019B5
Stirling's approximation for $n!$ states for some constants $c_1,c_2$ $c_1 n^{n+\frac{1}{2}}e^{n} \leq n! \leq c_2 n^{n+\frac{1}{2}}e^{n}.$ What are the tightest asymptotic bounds that can be placed on $n!$ $?$ ... $n! =\Theta((\frac{n}{e})^{n+\frac{1}{2}})$ $n! =\Theta(n^{n+\frac{1}{2}}2^{n})$
asked
Dec 18, 2018
in
Algorithms
by
Arjun
Veteran
(
431k
points)

369
views
tifr2019
algorithms
asymptoticnotations
0
votes
0
answers
13
Testbook Test Series: Algorithms  Asymptotic Analysis
a , c , d all three are right answer please explain if i am wrong.
asked
Dec 15, 2018
in
Algorithms
by
Abhishek Kumar 38
(
117
points)

76
views
testbooktestseries
algorithms
asymptoticnotations
0
votes
0
answers
14
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
(
3.2k
points)

66
views
algorithms
timecomplexity
asymptoticnotations
+1
vote
3
answers
15
Gateforum Test Series: Algorithms  Asymptotic Notations
Which of the following is not true in the function $f(n)=2^{n4}$? $f(n)$=Θ($2^{n+3}$) $f(n)$=Ω($n^{1000}$) $f(n)$=Ο($2^{n10}$) $f(n)$=$None$
asked
Dec 7, 2018
in
Algorithms
by
Gupta731
Active
(
4.8k
points)

135
views
gateforumtestseries
algorithms
asymptoticnotations
0
votes
1
answer
16
Gateforum Test Series: Algorithms  Asymptotic Notations
Consider the following function $f(x)$ = $x^8$+6$x^7$9$x^5$$x^4$+2$x^2$18. Which of the following is true if x is greater than 56? $f(x)$ = O($x^8$) $f(x)$ = Ω($x^8$) $f(x)$ = θ($x^8$) $f(x)$ = None of the above.
asked
Dec 7, 2018
in
Algorithms
by
Gupta731
Active
(
4.8k
points)

127
views
gateforumtestseries
algorithms
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
(
883
points)

42
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
(
263
points)

96
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
(
29k
points)

89
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.8k
points)

151
views
asymptoticnotations
recurrence
+1
vote
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
(
2.4k
points)

177
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
Veteran
(
58.8k
points)

79
views
algorithms
asymptoticnotations
growthrate
+1
vote
2
answers
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
Veteran
(
58.8k
points)

117
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
(
447
points)

51
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
(
5.2k
points)

134
views
timecomplexity
algorithms
asymptoticnotations
recurrence
0
votes
1
answer
26
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
Boss
(
12.9k
points)

57
views
asymptoticnotations
+1
vote
1
answer
27
MadeEasy Test Series: Algorithms  Asymptotic Notations
asked
Oct 3, 2018
in
Algorithms
by
mitesh kumar
Junior
(
569
points)

86
views
algorithms
asymptoticnotations
madeeasytestseries
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
(
17.6k
points)

101
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
29
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, 2018
in
Algorithms
by
sushmita
Boss
(
17.6k
points)

139
views
timecomplexity
asymptoticnotations
algorithms
0
votes
4
answers
30
Can we solve the recurrence T(n) = T(n/2) + 2^n by masters theorem, if possible?
asked
Sep 28, 2018
in
Algorithms
by
mohitrai0_0
(
387
points)

705
views
recurrence
algorithms
mastertheorem
timecomplexity
asymptoticnotations
Page:
« prev
1
2
3
4
5
6
7
...
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
@ben10 There are two questions in it, as per time...
Is official answer key out ??
https://gateoverflow.in/331364/isro202036 ,...
For the postorder to preorder conversion, please...
Getting 111 marks. If big endian option changes...
50,737
questions
57,284
answers
198,183
comments
104,862
users