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
3
answers
1
By own
$if ...F(n)=O(g(n)) Then ...it is true or false 2^{f(n)}=O(2^{g(n)}) Answer with reason$
asked
Sep 22
in
Algorithms
by
shubhamkks1005
(
5
points)

54
views
asymptoticnotations
0
votes
2
answers
2
From asymptotic notation
F(n)=O{ [ f(n)]^2} This statement is true or false With reason..
asked
Sep 22
in
Algorithms
by
shubhamkks1005
(
5
points)

31
views
asymptoticnotations
0
votes
1
answer
3
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.7k
points)

20
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
4
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.7k
points)

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

27
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
6
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)

96
views
algorithms
mastertheorem
timecomplexity
asymptoticnotations
+3
votes
1
answer
7
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
(
20.6k
points)

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

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

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

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

116
views
asymptoticnotations
timecomplexity
0
votes
0
answers
12
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.7k
points)

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

7
views
cormen
algorithms
asymptoticnotations
0
votes
0
answers
14
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.7k
points)

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

34
views
cormen
algorithms
asymptoticnotations
descriptive
difficult
+1
vote
0
answers
16
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.7k
points)

12
views
cormen
algorithms
asymptoticnotations
descriptive
difficult
0
votes
0
answers
17
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.7k
points)

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

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

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

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

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

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

33
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
24
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.7k
points)

22
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
25
#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
(
281
points)

25
views
asymptoticnotations
0
votes
2
answers
26
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
(
175
points)

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

64
views
asymptoticnotations
algorithms
0
votes
1
answer
28
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.3k
points)

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

42
views
asymptoticnotations
algorithms
+1
vote
0
answers
30
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
(
199
points)

91
views
asymptoticnotations
algorithms
timecomplexity
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
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Minimal Deterministic Finite Automata
To be aware of fake GATE test series
Standard Book Exercise Questions for Computer Science
Follow @csegate
Recent questions tagged asymptoticnotations
Recent Blog Comments
Favorite is not working for blogs.. In favorites...
Favourite option does work. But list options...
Blog favorite button doesnt work?
@Arjun Sir can we have an option to save such...
Thanks Sir
50,666
questions
56,163
answers
193,778
comments
93,863
users