Dark Mode

Recent questions tagged asymptotic-notation

0 votes

0 answers

151

#Self-Doubt #Asymptotic-Notation
Is it true? $an^{2} = O(n^{2})$ for a>0 Also, what is the difference between Small-oh and Big-oh? Also, why we consider theta, omega as Big-oh sometimes, in the above problem, the answer is Big-theta but it is equal to big-oh. Why is it so?

nishant_magarde asked in Algorithms Mar 21, 2019

by nishant_magarde

464 views

0 votes

2 answers

152

Self doubt
O(n-1)+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?

Tanuj Guha Thakurta asked in Algorithms Mar 19, 2019

by Tanuj Guha Thakurta

479 views

0 votes

1 answer

153

Rosen ch.3
Q.1 :Give a big-O estimate for f(n)=3n log(n!) + ($n^2$+3)log n, where n is positive integer Answer is given as O($n^2$ logn), Why it is not O($n^3$)? Q.2: Find the least integer n such that f(x) is O($x^n$) f(x)=2$x^2$ + $x^3$logx here n is given as 4, why it can not be 3??

himgta asked in Algorithms Mar 12, 2019

by himgta

983 views

2 votes

1 answer

154

Asymptotic Notations
Q1) f(n) = n^(1-sin n) g(n) = n^(1+cos n) Relation between them ? Q2) f(n) = n^(1-sin n) g(n) = n^(2+cos n ) Relation between them ?

Ashish Roy 1 asked in Algorithms Mar 7, 2019

by Ashish Roy 1

1.2k views

1 vote

1 answer

155

Time Complexity
I am unable to Find its time complexity using Iterative method… Will any one help me out with this . Thank you :)

Nandkishor3939 asked in Algorithms Jan 18, 2019

by Nandkishor3939

696 views

1 vote

1 answer

156

Applied Course | Mock GATE | Test 1 | Question: 56
$\text{O}, \Omega,$ and $\Theta$ denote Big-Oh, Big-Omega and Big-Theta notations respectively. Which of the following statement is not correct? $n \: \log a = \Omega (\log ^2 (n)), \text{ where a is a constant >1}$ ... $4(n+k)^m = \text{O} (n^m), \text{ where m is a constant >1}$ $n+\log (n) = \Theta (n)$

Applied Course asked in Algorithms Jan 16, 2019

by Applied Course

570 views

0 votes

1 answer

157

asymptotic notation
O(n) O(Log n) O(Log log n) none

gate_forum asked in Algorithms Jan 13, 2019

489 views

0 votes

0 answers

158

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.

debanjan sarkar asked in Algorithms Jan 12, 2019

by debanjan sarkar

445 views

1 vote

1 answer

159

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)

bts1jimin asked in Algorithms Jan 12, 2019

561 views

0 votes

1 answer

160

Algorithms Time complexity

Rackson asked in Programming in C Jan 12, 2019

937 views

0 votes

2 answers

161

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?

snaily16 asked in Algorithms Jan 9, 2019

572 views

1 vote

1 answer

162

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?

Markzuck asked in Algorithms Jan 6, 2019

503 views

0 votes

1 answer

163

UPPCL AE 2018:72
The recurrence equation $T(n) = T(\sqrt{n}) + O(1)$ has the following asymptotic solution: $T(n) = O(\sqrt{n})$ $T(n) = O(\log n)$ $T(n) = O(n^{1/\log n})$ $T(n) = O(\log \log n)$

admin asked in Algorithms Jan 5, 2019

by admin

286 views

0 votes

1 answer

164

UPPCL AE 2018:38
Which of the given options provides the increasing order of asymptotic complexity of functions $\text{f}_{1}, \text{f}_{2}, \text{f}_{3}$ and $ \text{f}_{4} $ ... $\text{f}_{4}, \text{f}_{3}, \text{f}_{2}, \text{f}_{1}$

admin asked in Algorithms Jan 5, 2019

by admin

438 views

1 vote

1 answer

165

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})$

shreyansh jain asked in Algorithms Jan 4, 2019

by shreyansh jain

898 views

0 votes

0 answers

166

#algorithm
Write the Big-O 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

amit166 asked in Algorithms Jan 4, 2019

462 views

0 votes

1 answer

167

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)

saptarshiDey asked in Algorithms Jan 3, 2019

by saptarshiDey

8.1k views

0 votes

1 answer

168

MadeEasy Test Series 2019: Algorithms - Time complexity
cant we write the recurrance relation for bar() as T(n) = 5T(n-1) + c, like cant we take both the recurrance call as combined as both have same parameter? and if not, then how to solve such?

Markzuck asked in Algorithms Dec 29, 2018

820 views

6 votes

1 answer

169

GATE Overflow | Mock GATE | Test 1 | Question: 48
Consider the following piece of pseudo-code: 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(n-1); } C(n){ return A (√n); } D(n){ return n; } What is the time complexity in ... $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n \log \log n)$ $\Theta(n^2 \log n)$

Ruturaj Mohanty asked in Algorithms Dec 27, 2018

by Ruturaj Mohanty

1.6k views

1 vote

0 answers

170

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)$

Shubhgupta asked in Algorithms Dec 26, 2018

731 views

0 votes

1 answer

171

#timecomplexity
What is difference between tightest upper bound and tightest lower bound? Give ur explanation with examples?

Deepesh Pai asked in Algorithms Dec 25, 2018

368 views

10 votes

2 answers

172

TIFR CSE 2019 | Part B | Question: 5
Stirling's approximation for $n!$ states for some constants $c_1,c_2$ $c_1 n^{n+\frac{1}{2}}e^{-n} \leq n! \leq c_2 n^{n+\frac{1}{2}}e^{-n}.$ What are the tightest asymptotic bounds that can be placed on $n!$ $?$ ... $n! =\Theta((\frac{n}{e})^{n+\frac{1}{2}})$ $n! =\Theta(n^{n+\frac{1}{2}}2^{-n})$

Arjun asked in Algorithms Dec 18, 2018

by Arjun

3.4k views

0 votes

1 answer

173

Testbook Test Series: Algorithms - Asymptotic Analysis
a , c , d all three are right answer please explain if i am wrong.

Abhishek Kumar 38 asked in Algorithms Dec 15, 2018

by Abhishek Kumar 38

343 views

0 votes

1 answer

174

Question_bank
f(n)=O(g(n)) Which of the following is True? 2^f(n)=O(2^(g(n)) log(f(n))=O(log(g(n)) f(n)=O(f(n/2)) f(n)=O(f(n)^2)

Shivam Kasat asked in Algorithms Dec 10, 2018

by Shivam Kasat

531 views

1 vote

3 answers

175

Gateforum Test Series: Algorithms - Asymptotic Notations
Which of the following is not true in the function $f(n)=2^{n-4}$? $f(n)$=Θ($2^{n+3}$) $f(n)$=Ω($n^{1000}$) $f(n)$=Ο($2^{n-10}$) $f(n)$=$None$

Gupta731 asked in Algorithms Dec 7, 2018

560 views

0 votes

1 answer

176

Gateforum Test Series: Algorithms - Asymptotic Notations
Consider the following function $f(x)$ = $x^8$+6$x^7$-9$x^5$-$x^4$+2$x^2$-18. Which of the following is true if x is greater than 56? $f(x)$ = O($x^8$) $f(x)$ = Ω($x^8$) $f(x)$ = θ($x^8$) $f(x)$ = None of the above.

Gupta731 asked in Algorithms Dec 7, 2018

685 views

0 votes

0 answers

177

MadeEasy test series

shweta sah asked in Algorithms Dec 2, 2018

231 views

0 votes

1 answer

178

MadeEasy test series

shweta sah asked in Algorithms Dec 2, 2018

458 views

1 vote

0 answers

179

Made easy test series
Order the following: $\frac{e^{n \log n}}{n}, 2^{n \log n}, n^{\sqrt n}$

shweta sah asked in Algorithms Dec 2, 2018

396 views

1 vote

0 answers

180

Self Doubt
A.2^(loglogn)^2, B.(2^(root(logn)) Asymptotic Order

Abhisek Tiwari 4 asked in Algorithms Dec 1, 2018

by Abhisek Tiwari 4

423 views

Page:

« prev
1
2
3
4
5
6
7
8
9
10
11
...
19
next »

Recent questions tagged asymptotic-notation