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
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
1
answer
1
Master's Theorem: Validity of Format
How to check if a given recurrence relation is in a format that is valid to apply Master’s Theorem? Also, how to distinguish between Master’s Theorem and extended Master’s Theorem?
asked
3 days
ago
in
Algorithms
by
lolster
(
223
points)

41
views
algorithms
mastertheorem
timecomplexity
asymptoticnotations
0
votes
0
answers
2
#CLRS #Algorithm Doubt about randomized QuickSort.
asked
May 27
in
Algorithms
by
iarnav
Loyal
(
7.9k
points)

75
views
algorithms
sortingalgorithmsquicksort
sorting
asymptoticnotations
0
votes
1
answer
3
Asymptotic Notation theta property
If $T1(n) = \Theta(f(n))$ & $T2(n) = \Theta(f(n))$ Then, Is $T1(n) + T2(n) = O(f(n))$ If yes, then how?
asked
May 26
in
Algorithms
by
shubhojit1412
(
5
points)

74
views
asymptoticnotations
algorithms
timecomplexity
growthrate
0
votes
0
answers
4
What would be the upper and lower bound for this decreasing function or invalid case? #Algorithm #Asymtoticnotations
asked
May 10
in
Algorithms
by
aniketpatil32
(
29
points)

25
views
#algorithms
asymptoticnotations
+1
vote
0
answers
5
Find Asymptotic upper bound (http://www.csd.uwo.ca/~moreno/CS433CS9624/Resources/master.pdf)
asked
Apr 19
in
Algorithms
by
Mk Utkarsh
Boss
(
34.5k
points)

83
views
asymptoticnotations
timecomplexity
0
votes
0
answers
6
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
(
40.4k
points)

13
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
7
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
(
40.4k
points)

3
views
cormen
algorithms
asymptoticnotations
0
votes
0
answers
8
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
(
40.4k
points)

6
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
9
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
(
40.4k
points)

23
views
cormen
algorithms
asymptoticnotations
descriptive
difficult
0
votes
0
answers
10
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
(
40.4k
points)

6
views
cormen
algorithms
asymptoticnotations
descriptive
difficult
0
votes
0
answers
11
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
(
40.4k
points)

3
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
12
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
(
40.4k
points)

8
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
13
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
(
40.4k
points)

53
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
14
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
(
40.4k
points)

11
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
15
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
(
40.4k
points)

42
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
16
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
(
40.4k
points)

11
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
17
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
(
40.4k
points)

25
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
18
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
(
40.4k
points)

13
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
19
#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
(
245
points)

18
views
asymptoticnotations
0
votes
2
answers
20
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
(
151
points)

58
views
timecomplexity
asymptoticnotations
+1
vote
1
answer
21
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
(
167
points)

47
views
asymptoticnotations
algorithms
0
votes
1
answer
22
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
(
1k
points)

103
views
timecomplexity
algorithms
asymptoticnotations
0
votes
0
answers
23
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
(
3.8k
points)

31
views
asymptoticnotations
algorithms
0
votes
0
answers
24
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
(
193
points)

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

52
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
26
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
(
239
points)

39
views
algorithms
asymptoticnotations
0
votes
0
answers
27
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
(
571
points)

50
views
algorithms
asymptoticnotations
madeeasytestseries
timecomplexity
0
votes
0
answers
28
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)

100
views
timecomplexity
asymptoticnotations
algorithms
0
votes
0
answers
29
#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
in
Algorithms
by
amit166
(
459
points)

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

218
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
The day that made me an IIScian :)
Unanswered Previous year GATE/TIFR questions
From being a Failure to getting into IISc  (Rank 888, Score 692)
My interview experience at IITs/IISc
IIT Delhi CSE Mtech interview 14 may
Follow @csegate
Recent questions tagged asymptoticnotations
Recent Blog Comments
Congratulations 👍 Very nice experience 😊
Congo :) U deserve it :)
Address will be confirmed again before shipping ...
sir by mistake I have given my home address...
Corrected now 👍
49,541
questions
54,071
answers
187,187
comments
70,978
users