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
Cormen Edition 3 Exercise 3.2 Question 8 (Page No. 60)
Show that $K$ $ln$ $K = \Theta (n)$ implies $k=$\Theta$($n$/$ln$ $n$)$.
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

10
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
2
Cormen Edition 3 Exercise 3.2 Question 7 (Page No. 60)
Prove by induction that the $i^{th}$ Fibonacci number satisfies the equality $F_i = \frac{\phi^i\hat{\phi^i}}{\sqrt{5}}$ where $\phi$ is the golden ratio and $\hat{\phi}$ is its conjugate.
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

3
views
cormen
algorithms
asymptoticnotations
0
votes
0
answers
3
Cormen Edition 3 Exercise 3.2 Question 6 (Page No. 60)
Show that the golden ratio $\phi$ and its conjugate $\hat{\phi}$ both satisfy the equation $x^2=x+1$.
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

2
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
4
Cormen Edition 3 Exercise 3.2 Question 5 (Page No. 60)
Which is asymptotically larger: $lg(lg^*n)$ and $lg^*(lg n)$ ?
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

4
views
cormen
algorithms
asymptoticnotations
descriptive
difficult
0
votes
0
answers
5
Cormen Edition 3 Exercise 3.2 Question 4 (Page No. 60)
Is the function $\lceil$ $lg$ $n$ $\rceil$!$ polynomially bounded ? Is the function $\lceil$ $lg$ $lg$ $n$ $\rceil$!$ polynomially bounded ?
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

4
views
cormen
algorithms
asymptoticnotations
descriptive
difficult
0
votes
0
answers
6
Cormen Edition 3 Exercise 3.2 Question 1 (Page No. 60)
Show that if $f(n)$ and $g(n)$ are monotonically increasing functions, then so are the functions $f(n) +g(n)$ and $f(g(n))$, and if $f(n)$ and $g(n)$ are in addition nonnegative, then $f(n) . g(n)$ is monotonically increasing.
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

3
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
7
Cormen Edition 3 Exercise 3.1 Question 8 (Page No. 53)
We can extend our notation to the case of two parameters $n$ and $m$ that can go to infinity independently at different rates.For a given function $g(n,m)$, we denote by $O(g(n,m))$ the set of functions $O(g(n,m))$ $=$ {$f(n,m) :$ ... all $n \geq n_0$ or $m \geq m_0$ } Give corresponding definitions for $\Omega(g(n,m))$ and $\Theta(g(n,m))$.
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

6
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
8
Cormen Edition 3 Exercise 3.1 Question 7 (Page No. 53)
Prove that $o(g(n)) \cap \omega(g(n))$ is the empty set.
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

42
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
9
Cormen Edition 3 Exercise 3.1 Question 6 (Page No. 53)
Prove that the running time of an algorithm is $\Theta (g(n))$ if and only if its worstcase running time is $O(g(n))$ and its bestcase running time is $\Omega(g(n))$.
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

9
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
10
Cormen Edition 3 Exercise 3.1 Question 4 (Page No. 53)
Is $2^{n+1} = O(2^n) $? $2^{2n} = O(2^n)$?$
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

33
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
11
Cormen Edition 3 Exercise 3.1 Question 3 (Page No. 53)
Explain why the statement, “The running time of algorithm A is at least $O(n^2),$” is meaningless.
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

11
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
12
Cormen Edition 3 Exercise 3.1 Question 2 (Page No. 52)
Show that for any real constants $a$ and $b$, where $b > 0,$ $(n+a)^b=\Theta(n^b)$
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

22
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
13
Cormen Edition 3 Exercise 3.1 Question 1 (Page No. 52)
Let $f(n)$ and $g(n)$ be asymptotically nonnegative functions. Using the basic definition of $\Theta$ notation, prove that $max(f(n),g(n)) = \Theta(f(n)+g(n))$.
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

11
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
14
#SelfDoubt #AsymptoticNotation
Is it true? $an^{2} = O(n^{2})$ for a>0 Also, what is the difference between Smalloh and Bigoh? Also, why we consider theta, omega as Bigoh sometimes, in the above problem, the answer is Bigtheta but it is equal to bigoh. Why is it so?
asked
Mar 21
in
Algorithms
by
nishant_magarde
(
239
points)

14
views
asymptoticnotations
0
votes
2
answers
15
Self doubt
O(n1)+O(n)=O(n) O(n/2)+O(n)=O(n) but O(1)+O(2)+O(3)+...+O(n)=O(n(n+1)/2)=O(n^2) why?
asked
Mar 19
in
Algorithms
by
Tanuj Guha Thakurta
(
153
points)

41
views
timecomplexity
asymptoticnotations
+1
vote
1
answer
16
Asymptotic Notations
Q1) f(n) = n^(1sin n) g(n) = n^(1+cos n) Relation between them ? Q2) f(n) = n^(1sin n) g(n) = n^(2+cos n ) Relation between them ?
asked
Mar 7
in
Algorithms
by
Ashish Roy 1
(
213
points)

42
views
asymptoticnotations
algorithms
0
votes
1
answer
17
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)

93
views
timecomplexity
algorithms
asymptoticnotations
0
votes
0
answers
18
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)

25
views
asymptoticnotations
algorithms
0
votes
0
answers
19
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
(
273
points)

54
views
asymptoticnotations
algorithms
timecomplexity
0
votes
0
answers
20
Algorithms Time complexity
asked
Jan 12
in
Programming
by
Rackson
Active
(
1.9k
points)

45
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
21
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
(
263
points)

35
views
algorithms
asymptoticnotations
0
votes
0
answers
22
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
in
Algorithms
by
Markzuck
Junior
(
643
points)

41
views
algorithms
asymptoticnotations
madeeasytestseries
timecomplexity
0
votes
0
answers
23
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.2k
points)

90
views
timecomplexity
asymptoticnotations
algorithms
0
votes
0
answers
24
#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
(
761
points)

20
views
big
asymptoticnotations
0
votes
1
answer
25
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
(
91
points)

130
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
26
time complexity
asked
Dec 30, 2018
in
Algorithms
by
Rahul_Rathod_
Junior
(
561
points)

33
views
timecomplexity
algorithms
asymptoticnotations
recurrence
0
votes
0
answers
27
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
(
643
points)

72
views
timecomplexity
algorithms
madeeasytestseries
asymptoticnotations
+3
votes
1
answer
28
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)

240
views
go2019flt1
asymptoticnotations
recurrence
+1
vote
0
answers
29
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.6k
points)

73
views
asymptoticnotations
0
votes
1
answer
30
#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
Junior
(
507
points)

28
views
timecomplexity
algorithms
asymptoticnotations
Page:
1
2
3
4
5
6
...
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
How to prepare for IISC Interdisciplinary Mathematical Sciences Interview
GO Hardcopy for GATE 2020
How to prepare for BARC interview
IIIT H
Tips for COAP2019
Follow @csegate
Recent questions tagged asymptoticnotations
Recent Blog Comments
What is the cutoff for M.Tech AI at IISc?
Yup. Hard copy contains a unique QR code for...
Lol. I got left out of IIT Kanpur GATE cutoff by...
Don't worry brother... i hope fate is also get...
50,049
questions
53,194
answers
184,531
comments
70,402
users