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
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
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
Cormen Edition 3 Exercise 8.1 Question 2 (Page No. 194)
Obtain asymptotically tight bounds on $lg\ (n!)$ without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k=1}^{n} lg\ k$.
asked
Jun 28
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

11
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
2
Cormen Edition 3 Exercise 3.2 Question 3 (Page No. 60)
Prove that $n!=\omega(2^n)$ and $n!=o(n^n)$.
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

13
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
3
Cormen Edition 3 Exercise 2.2 Question 4 (Page No. 29)
How can we modify almost any algorithm to have a good bestcase running time?
asked
Jun 25
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

22
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
4
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
Jun 12
in
Algorithms
by
lolster
(
233
points)

78
views
algorithms
mastertheorem
timecomplexity
asymptoticnotations
+3
votes
1
answer
5
asymptotic_Notations Self_Doubt
Please give an example case for which all the three conditions $f(n)\neq O(g(n))$, $f(n)\neq \Theta (g(n))$ and $f(n)\neq \Omega (g(n))$ holds true.
asked
Jun 1
in
Algorithms
by
Satbir
Boss
(
17.3k
points)

173
views
asymptoticnotations
selfdoubt
algorithms
0
votes
0
answers
6
#CLRS #Algorithm Doubt about randomized QuickSort.
asked
May 27
in
Algorithms
by
iarnav
Loyal
(
8k
points)

87
views
algorithms
sortingalgorithmsquicksort
sorting
asymptoticnotations
0
votes
1
answer
7
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)

115
views
asymptoticnotations
algorithms
timecomplexity
growthrate
0
votes
0
answers
8
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)

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

105
views
asymptoticnotations
timecomplexity
0
votes
0
answers
10
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
(
41.3k
points)

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

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

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

26
views
cormen
algorithms
asymptoticnotations
descriptive
difficult
+1
vote
0
answers
14
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
(
41.3k
points)

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

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

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

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

14
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
19
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
(
41.3k
points)

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

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

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

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

22
views
asymptoticnotations
0
votes
2
answers
24
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
(
155
points)

65
views
timecomplexity
asymptoticnotations
+1
vote
1
answer
25
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)

57
views
asymptoticnotations
algorithms
0
votes
1
answer
26
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.1k
points)

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

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

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

54
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
30
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)

45
views
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged asymptoticnotations
Recent Blog Comments
Refund time depends on the payment mode ...
@Arjun Sir , when can i expect my refund in the...
This book is returned you can enable a pay now...
@Pranavcool The book stocks are over and no one...
@Lokesh Thats unfortunate. I have refunded you....
49,830
questions
54,802
answers
189,511
comments
80,751
users