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, 2019
in
Algorithms
by
shubhamkks1005
(
5
points)

73
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, 2019
in
Algorithms
by
shubhamkks1005
(
5
points)

46
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

22
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

21
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

30
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, 2019
in
Algorithms
by
lolster
(
237
points)

114
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, 2019
in
Algorithms
by
Satbir
Boss
(
23.9k
points)

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

520
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, 2019
in
Algorithms
by
shubhojit1412
(
5
points)

163
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, 2019
in
Algorithms
by
aniketpatil32
(
29
points)

41
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, 2019
in
Algorithms
by
Mk Utkarsh
Boss
(
36.5k
points)

121
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

21
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

8
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

11
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

40
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

13
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

20
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

71
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

20
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

54
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

23
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

37
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

26
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, 2019
in
Algorithms
by
nishant_magarde
(
319
points)

32
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, 2019
in
Algorithms
by
Tanuj Guha Thakurta
(
175
points)

84
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, 2019
in
Algorithms
by
Ashish Roy 1
(
167
points)

69
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, 2019
in
Algorithms
by
Nandkishor3939
Active
(
1.3k
points)

125
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, 2019
in
Algorithms
by
debanjan sarkar
Active
(
3.8k
points)

47
views
asymptoticnotations
algorithms
+2
votes
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, 2019
in
Algorithms
by
bts1jimin
(
205
points)

100
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
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
Very slim chances..FML
100 percent
I am getting 151 marks excluding question not...
everyone will be surprised seeing the cutoff this...
There is no point of any debate/discourse here....
50,737
questions
57,292
answers
198,235
comments
104,918
users