Dark Mode

Recent questions tagged asymptotic-notation

3 votes

0 answers

301

Algo:- Small oh notataion
This is a snapshot from coreman. Here if i want to prove this example $2n^2$ = $o(n^2)$ And if i take c=3, then $2n^2$ < $3n^2$ Now for all n0 and c=3 it will hold and this will be true .I know this proof i gave is wrong.But what exactly is wrong ?

rahul sharma 5 asked in Algorithms Nov 14, 2017

by rahul sharma 5

304 views

1 vote

1 answer

302

time complexity
Consider the following functions for large values on n f(n) = n1/root(logn) g(n)=root(logn) h(n)=n1/100 1.g(n)<f(n)<h(n) 2.g(n)<h(n)<f(n)

A_i_$_h asked in Algorithms Nov 14, 2017

289 views

4 votes

1 answer

303

time complexity
Determine the time complexity of the program segment given below: i= n; while (i>0) { k=1; for (j=1; j<=n; j+=k) { k++; } i= i/2; } (A) O(n2) (B) O(n.log n) (C) O(log2 n) (D) O(log n√n)

Parshu gate asked in Algorithms Nov 11, 2017

3.1k views

4 votes

0 answers

304

Asymptotic Notation
Assume that f(n) and g(n) are two functions, such that f(n)=O(g(n)). Which of the following always hold? A)$f(n)=O((f(n))^{2})$ B)$f(n)=\Omega ((f(n))^{2})$ C)$g(n)=O ((f(n))^{2})$ D)$g(n)=\Omega (g(n))$

srestha asked in Algorithms Nov 10, 2017

1.1k views

3 votes

1 answer

305

Arrange the following functions in asymptotically increasing order
Arrange the following functions in asymptotically increasing order f1(n) = n0.999999 log n f2(n) = 10000000n f3(n) = 1.000001n f4(n) = n2 Ans is f1, f2, f4, f3 I am not understanding how f1(n) grows asymptotically slower than f2(n)

sunil sarode asked in Algorithms Nov 10, 2017

by sunil sarode

7.4k views

2 votes

1 answer

306

How to determine the time complexity of this loop?
// func() is any constant root function for (int i = n; i > 0; i = func(i)) { // some O(1) expressions or statements } "In this case, i takes values n, n1/k, (n1/k)1/k = n1/k2, ... do we calculate that there are logk(log(n)) iterations? Source: http://www.geeksforgeeks.org/time-complexity-loop-loop-variable-expands-shrinks-exponentially/

Narasimhan asked in Algorithms Nov 7, 2017

1.0k views

0 votes

2 answers

307

Fibonacci Series Complexity
PLEASE EXPLAIN HOW TO APPROACH THESE KIND OF PROBLEMS

Parshu gate asked in Algorithms Nov 5, 2017

691 views

5 votes

2 answers

308

Time Complexity
Consider the following function Void func(int n){ Int k=n; Int i=0; for(;i<n;i++){ while(k>1){ k>>=1; } } What is the worst case time complexity of the function?

shaurya vardhan asked in Algorithms Nov 2, 2017

by shaurya vardhan

1.6k views

4 votes

1 answer

309

Time Complexity
Consider the following code….. Search(int n){ if(n<2) then return; else{ s=0; for(i=1;i<=8;i++){ Search(n/2); } for(i=1;i<n*n;i++){ for(j=1;j<n;j=j*2){ s=s+i; } } } } Assume s is a global variable.Find the complexity of the given Search(n)?

shaurya vardhan asked in Algorithms Nov 2, 2017

by shaurya vardhan

653 views

1 vote

1 answer

310

Asymptotic
which is asymptotically greater n or $2^{logn}$

learner_geek asked in Algorithms Oct 30, 2017

by learner_geek

296 views

1 vote

1 answer

311

I have a basic question regarding DAA
let a function f(x) =$n^3$+$n^4$+1 so which are true 1. θ($n^4$) 2. θ($n^5$) 3. θ(1) 4. θ($n^3$) 5. Ω ($n^4$) 6. Ω ($n^5$) 7. Ω (1) 8. Ω ($n^3$) 9. O ($n^4$) 10. O ($n^5$) 11. O (1) 12. O ($n^3$) PLZ GIVE EXPLANATION WHICH ONE IS TRUE OR FALSE.

hem chandra joshi asked in Algorithms Oct 29, 2017

by hem chandra joshi

362 views

4 votes

1 answer

312

What can be the big oh?
What will be the Big Oh for $n!$ ? As we can deduce log($n!$) = O(log n) . Is there any proof like we have for log($n!$) ?

Manish Chetwani asked in Algorithms Oct 23, 2017

by Manish Chetwani

367 views

2 votes

1 answer

313

doubt
https://gateoverflow.in/30720/tifr2016-b-7 the above question is already discussed but still am not clear enuf can someone help

A_i_$_h asked in Algorithms Oct 22, 2017

418 views

2 votes

1 answer

314

analysis-of-algorithms
If f(n) = O(g(n)) then is it always true g(n) = (f(n)) ??? please explain.

mohit kumar 5 asked in Algorithms Oct 19, 2017

by mohit kumar 5

375 views

5 votes

1 answer

315

Algo: Time complexity
T(n) = 4T(n/2) + n2.$\sqrt{2}$ In thetha notation?

rahul sharma 5 asked in Algorithms Oct 18, 2017

by rahul sharma 5

714 views

0 votes

1 answer

316

complexity
1.(n + a)b = $\Omega$(nb) for all real numbers a , b >0 2.na+1=theta(nb) iff a=b for all real numbers a , b>0 which is true? Acyclic graph directory structure is more flexible than simple tree structure - true or false

A_i_$_h asked in Algorithms Oct 17, 2017

327 views

4 votes

1 answer

317

GATEFORUM
for(i=0;i<=n;i++){ for(j=0;j<=i2;j++){ for(k=0;k<=$\frac{n}{2}$;k++){ x=y+z; }}} How many times the x=y+z statement will execute?

Abhi Girin asked in Programming in C Oct 16, 2017

1.1k views

2 votes

2 answers

318

time complexity
A) T(n) = 2T(root(n)) + 1 ; n>2 T(n) =1 ; 0 < n <= 2 B) f(n) =n g(n) = n(1+sin n) where n is positive integer which is true? 1.f(n) = O(g(n)) 2.f(n) = $\Omega$(g(n))

A_i_$_h asked in Algorithms Oct 16, 2017

623 views

0 votes

0 answers

319

Time complexity

dragonball asked in Algorithms Oct 15, 2017

568 views

1 vote

2 answers

320

Aymptotic notation
Consider $\sum_{i=0}^n{}$ i3 =x.what can be X 1.theta(n4) 2.theta(n5) 3.O(n5) 4.$\Omega$(n3)

A_i_$_h asked in Algorithms Oct 15, 2017

402 views

2 votes

1 answer

321

Asymptotic time order

dragonball asked in Algorithms Oct 15, 2017

869 views

1 vote

2 answers

322

Algo doubt
iterated logarithmic function is defined as $\log^*n = \begin{cases} 0 &\text{if }\quad n\leq 0 \\1 +\log^*(\log n) &\text{if } \quad n >1\end{cases}$ Which of the following is true? $\log^*n = O(\log(\log n ))$ $(\log^*n)!= O(\log n)$ $\log^* n = \Theta(\log n)$ $(\log^*n)^n= O((\log n)!)$

Surya Dhanraj asked in Algorithms Oct 15, 2017

by Surya Dhanraj

798 views

3 votes

1 answer

323

Time complexity
Solve the following recurrence relation $T(n)=4T(n/2)+n^2 \sqrt 2$

Shivi rao asked in Algorithms Oct 9, 2017

772 views

3 votes

1 answer

324

Time complexity
f(n)=Ω(n),g(n)=O(n) than what is f(n).g(n)

Shivi rao asked in Algorithms Oct 9, 2017

404 views

1 vote

1 answer

325

asymptotic function order
Rank the following functions by increasing order of growth. That is, find any arrangement $g_1, g_2, g_3, g_4, g_5, g_6, g_7$ of the functions satisfying: $g_1 = O(g_2), g_2 = O(g_3), g_3 = O(g_4), g_4 = O(g_5), g_5 = O(g_6), g_6 = O(g_7).$ $f_1(n) = n^4 + \log n$ ... $f_3(n) = n \log n$ $f_4(n) = nC_3$ $f_5(n) = nC_{n/2}$ $f_6(n) = 2^n$ $f_7(n) = n^{\log n}$

Hira Thakur asked in Algorithms Oct 5, 2017

2.9k views

0 votes

0 answers

326

Probability
Imagine you are given a bag of n balls. You are told that at least 10% of the balls are blue, and no more than 90% of the balls are red. Asymptotically (for large n) how many balls do you have to draw from the bag to see a blue ball with probability at least 2/3? (You can assume that the balls are drawn with replacement.)

Harish Karnam asked in Probability Sep 28, 2017

by Harish Karnam

299 views

0 votes

2 answers

327

[Algo] complexity
f(n) + o(f(n)) = thetha(f(n)) Does this hold? o is small -oh notation.

rahul sharma 5 asked in Algorithms Sep 25, 2017

by rahul sharma 5

381 views

0 votes

0 answers

328

Time complexity
class Solution { public: int getSum(int a, int b) { int total = a; while (b != 0) { total = a ^ b; //calculates sum of 'a' and 'b' without taking carry b = (a & b) << 1; //calculates the carry a = total; //add sum(without carry) and carry } return total; } }; What is the time complexity of the above code ?Plz describe.

dragonball asked in Algorithms Sep 21, 2017

202 views

0 votes

2 answers

329

Asymptotic notation

Nisha moyal asked in Algorithms Sep 19, 2017

2.0k views

0 votes

0 answers

330

asymptotic notation
T(n) = 2T( n / root(2)) + n T(1) = O(1) when i solve this i get theta ( n ^ log 2 base root(2)) using masters theorem after this how do i slove

A_i_$_h asked in Algorithms Sep 18, 2017

332 views

Page:

« prev
1
...
6
7
8
9
10
11
12
13
14
15
16
...
19
next »

Recent questions tagged asymptotic-notation