menu
search
Log In
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

Subjects

Recent questions tagged asymptotic-notations

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions tagged asymptotic-notations

3 votes
0 answers
1
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 ?
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 ?
asked Nov 14, 2017 in Algorithms rahul sharma 5 98 views
4 votes
1 answer
2
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)
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)
asked Nov 12, 2017 in Algorithms Parshu gate 1k views
4 votes
0 answers
3
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))$
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))$
asked Nov 10, 2017 in Algorithms srestha 354 views
2 votes
1 answer
4
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/
// 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, n1/k3, , n1/klogk(log(n)), so ... the above statement? How do we calculate that there are logk(log(n)) iterations? Source: http://www.geeksforgeeks.org/time-complexity-loop-loop-variable-expands-shrinks-exponentially/
asked Nov 7, 2017 in Algorithms Narasimhan 582 views
3 votes
1 answer
5
Time Complexity
T(n)=4 T(n/2) + n2 21/2 I have solved this by back substitution .. and it forms equations of the form 4k T(n/2k) + k n2 21/2 its giving time complexity as n2 + n2 log2n the answer is Theta(n2.5). i have two questions .. a) how can we get Theta(n2.5). b) is n2 log2n Asymptotically faster than n2 ?
T(n)=4 T(n/2) + n2 21/2 I have solved this by back substitution .. and it forms equations of the form 4k T(n/2k) + k n2 21/2 its giving time complexity as n2 + n2 log2n the answer is Theta(n2.5). i have two questions .. a) how can we get Theta(n2.5). b) is n2 log2n Asymptotically faster than n2 ?
asked Nov 5, 2017 in Algorithms shaurya vardhan 460 views
5 votes
2 answers
7
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?
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 shaurya vardhan 979 views
4 votes
1 answer
8
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)?
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 shaurya vardhan 240 views
4 votes
1 answer
9
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!$) ?
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 Manish Chetwani 184 views
1 vote
1 answer
10
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"); } } } }
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 Manish Chetwani 168 views
2 votes
1 answer
11
analysis-of-algorithms
If f(n) = O(g(n)) then is it always true g(n) = (f(n)) ??? please explain.
If f(n) = O(g(n)) then is it always true g(n) = (f(n)) ??? please explain.
asked Oct 19, 2017 in Algorithms mohit kumar 5 149 views
5 votes
1 answer
12
Algo: Time complexity
T(n) = 4T(n/2) + n2.$\sqrt{2}$ In thetha notation?
T(n) = 4T(n/2) + n2.$\sqrt{2}$ In thetha notation?
asked Oct 18, 2017 in Algorithms rahul sharma 5 288 views
3 votes
1 answer
13
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?
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 Abhi Girin 607 views
2 votes
1 answer
15
Asymptotic time order
asked Oct 15, 2017 in Algorithms dragonball 268 views
3 votes
1 answer
16
Time complexity
Solve the following recurrence relation $T(n)=4T(n/2)+n^2 \sqrt 2$
Solve the following recurrence relation $T(n)=4T(n/2)+n^2 \sqrt 2$
asked Oct 9, 2017 in Algorithms Shivi rao 276 views
3 votes
1 answer
17
Time complexity
f(n)=Ω(n),g(n)=O(n) than what is f(n).g(n)
f(n)=Ω(n),g(n)=O(n) than what is f(n).g(n)
asked Oct 9, 2017 in Algorithms Shivi rao 179 views
0 votes
0 answers
18
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.)
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 Harish Karnam 109 views
3 votes
1 answer
19
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 )
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 Harsh Mehta 380 views
0 votes
0 answers
20
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.
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 dragonball 105 views
0 votes
2 answers
21
Asymptotic notation
asked Sep 19, 2017 in Algorithms Nisha moyal 603 views
–1 vote
1 answer
23
Time Complexity
What will be the time complexity of a function f(n) = n^-2 i.e. pow (n,-2) ?
What will be the time complexity of a function f(n) = n^-2 i.e. pow (n,-2) ?
asked Sep 12, 2017 in Algorithms dragonball 174 views
2 votes
0 answers
24
time complexity
What is the time complexity of the following code snippet? Assume x is a global variable and “statement” takes O(n) time?
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 Warlock lord 321 views
2 votes
1 answer
25
time complexity
If F(n) = (log n)n then, is F(n) = O(n2) true? Also, what about F(n) = $\Theta$(n2)
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 Warlock lord 117 views
0 votes
1 answer
26
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++; } } } }
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 Warlock lord 226 views
1 vote
2 answers
27
Asymptotic notations
g(n)=Ώ(n) h(n)=O(n) g(n) . h(n) =?
g(n)=Ώ(n) h(n)=O(n) g(n) . h(n) =?
asked Sep 6, 2017 in Algorithms VS 227 views
1 vote
2 answers
28
Algorithms
Solve this T(n) = 0.5T(n/2)+1 ; T(1)=1
Solve this T(n) = 0.5T(n/2)+1 ; T(1)=1
asked Sep 1, 2017 in Algorithms Pavan Kumar Munnam 868 views
1 vote
3 answers
30
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:
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 Manu Thakur 1.1k views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...