Recent questions tagged asymptotic-notations

+5 votes

2 answers

1

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?

asked Nov 2, 2017 in Algorithms by shaurya vardhan Active (2.2k points) | 435 views

+4 votes

1 answer

2

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

asked Nov 2, 2017 in Algorithms by shaurya vardhan Active (2.2k points) | 182 views

+4 votes

1 answer

3

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

asked Oct 23, 2017 in Algorithms by Manish Chetwani (235 points) | 138 views

+1 vote

1 answer

4

Self Doubt
What will be the time complexity of the following code? A() { int i,j,k,n; for(i=1;i<=n;i++) { for(j=1;j<=i;j++) { for(k=1;k<=100;k++) { printf("ABCD"); } } } }

asked Oct 20, 2017 in Algorithms by Manish Chetwani (235 points) | 134 views

+2 votes

1 answer

5

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

asked Oct 19, 2017 in Algorithms by mohit kumar 5 Junior (581 points) | 117 views

+5 votes

1 answer

6

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

asked Oct 18, 2017 in Algorithms by rahul sharma 5 Boss (25.6k points) | 206 views

+3 votes

1 answer

7

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?

asked Oct 17, 2017 in Programming by Abhi Girin (413 points) | 509 views

0 votes

0 answers

8

Time complexity

asked Oct 15, 2017 in Algorithms by ashwina Active (1.8k points) | 117 views

+2 votes

1 answer

9

Asymptotic time order

asked Oct 15, 2017 in Algorithms by ashwina Active (1.8k points) | 90 views

+3 votes

1 answer

10

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

asked Oct 9, 2017 in Algorithms by Shivi rao Junior (537 points) | 199 views

+3 votes

1 answer

11

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

asked Oct 9, 2017 in Algorithms by Shivi rao Junior (537 points) | 141 views

0 votes

0 answers

12

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

asked Sep 28, 2017 in Probability by Harish Karnam Active (1.3k points) | 84 views

+3 votes

1 answer

13

Asymptotic Notation
What is the time complexity to find Kth minimum element from a doubly linked list having 'n' elements? (A) O (n log K ) (B) O (n log n ) (C) O (K log n ) (D) O ( n )

asked Sep 26, 2017 in Algorithms by Harsh Mehta Active (1.2k points) | 257 views

0 votes

0 answers

14

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.

asked Sep 21, 2017 in Algorithms by ashwina Active (1.8k points) | 84 views

0 votes

2 answers

15

Asymptotic notation

asked Sep 19, 2017 in Algorithms by Nisha moyal (15 points) | 289 views

0 votes

1 answer

16

time complexity

asked Sep 17, 2017 in Algorithms by Parshu gate Active (3.1k points) | 102 views

–1 vote

1 answer

17

Time Complexity
What will be the time complexity of a function f(n) = n^-2 i.e. pow (n,-2) ?

asked Sep 12, 2017 in Algorithms by ashwina Active (1.8k points) | 125 views

+2 votes

0 answers

18

time complexity
What is the time complexity of the following code snippet? Assume x is a global variable and “statement” takes O(n) time?

asked Sep 11, 2017 in Algorithms by Warlock lord Active (3.3k points) | 225 views

+2 votes

1 answer

19

time complexity
If F(n) = (log n)n then, is F(n) = O(n2) true? Also, what about F(n) = $\Theta$(n2)

asked Sep 11, 2017 in Algorithms by Warlock lord Active (3.3k points) | 93 views

0 votes

1 answer

20

time complexity
a[] is an array of integer, the size of the array is n. Read the following code snippet and find the time complexity of the code. int main(){ int i,j,k=0; for(i=0;i<n;i++){ for(j=0;j<i;j++){ while(k<i && a[j]<a[k]){ k++; } } } }

asked Sep 10, 2017 in Algorithms by Warlock lord Active (3.3k points) | 155 views

+1 vote

2 answers

21

Asymptotic notations
g(n)=Ώ(n) h(n)=O(n) g(n) . h(n) =?

asked Sep 6, 2017 in Algorithms by VS Boss (10.8k points) | 161 views

+1 vote

2 answers

22

Algorithms
Solve this T(n) = 0.5T(n/2)+1 ; T(1)=1

asked Sep 1, 2017 in Algorithms by Pavan Kumar Munnam Boss (10.7k points) | 363 views

+1 vote

1 answer

23

Time complexity of the given program.

asked Aug 31, 2017 in Algorithms by Rishabh Gupta 2 Boss (17.8k points) | 273 views

+1 vote

3 answers

24

Time Complexity of Iterative Program
The innermost loop will execute when j is multiple of i, and that will happen exactly i times. Please help me to find the time complexity of the below program:

asked Aug 29, 2017 in Algorithms by Manu Thakur Boss (44.1k points) | 604 views

+1 vote

1 answer

25

Asymptotic-Notations
Let f(n), g(n) & h(n) be 3 non-negative functions defined as follows: $f(n) = O(g(n))\; \; \; g(n) \neq O(f(n))$ $g(n) = O(h(n))\; \; \; h(n) = O(g(n))$ Which of the following is false? (A). f(n) + g(n) = O(h(n)) (B). f(n) = O(h(n)) (C). $h(n) \neq O(f(n))$ (D). $f(n).h(n) \neq O(g(n).h(n))$

asked Aug 23, 2017 in Algorithms by Victor0001 (23 points) | 121 views

+1 vote

1 answer

26

Asymptotic Notations
Let f(n), g(n) & h(n) be 3 non-negative functions defined as follows: $f(n) = O(g(n))\; \; \; g(n) \neq O(f(n))$ $g(n) = O(h(n))\; \; \; h(n) = O(g(n))$ Which of the following is false? (A). f(n) + g(n) = O(h(n)) (B). f(n) = O(h(n)) (C). $h(n) \neq O(f(n))$ (D). $f(n).h(n) \neq O(g(n).h(n))$

asked Aug 23, 2017 in Algorithms by Victor0001 (23 points) | 139 views

+1 vote

0 answers

27

Asymptotic Notation
Let f(n), g(n) & h(n) be 3 non-negative functions defined as follows: $f(n) = O(g(n))\; \; \; g(n) \neq O(f(n))$ $g(n) = O(h(n))\: \: \: h(n) = O(g(n))$ Which of the following is false? (A). f(n) + g(n) = O(h(n)) (B). f(n) = O(h(n)) (C). $h(n) \neq O(f(n))$ (D). $f(n).h(n) \neq O(g(n).h(n))$

asked Aug 23, 2017 in Algorithms by Victor0001 (23 points) | 210 views

+2 votes

1 answer

28

Coreman: Time Complexity
Can you please solve this following question further? What will be the time complexity?

asked Aug 18, 2017 in Algorithms by Manu Thakur Boss (44.1k points) | 504 views

+3 votes

2 answers

29

Doubt: Coreman: Relative Asymptotic growths: Que 01
f(n) = $n*2^{n}$ g(n) = $e^n$ What is the relation b/w the asymptotic time complexities of f(n) and g(n)?

asked Aug 15, 2017 in Algorithms by Manu Thakur Boss (44.1k points) | 171 views

+1 vote

1 answer

30

Coreman: Relative Asymptotic growths
Suppose $A = log^{k}n$ $B = n^{\epsilon} $ Assume that $ k\geq 1$ and $ \epsilon > 0$ What is the relation b/w the asymptotic time complexities of A and B? 1. A = O(B) 2. A = o(B) 3. A = $\Omega (B)$ 4. A = $\omega (B)$

asked Aug 14, 2017 in Algorithms by Manu Thakur Boss (44.1k points) | 258 views

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 questions tagged asymptotic-notations

Recent Posts

Recent Blog Comments