# Recent questions tagged asymptotic-notations

1
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 ?
2
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)
3
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))$
4
// 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/
5
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 ?
6
PLEASE EXPLAIN HOW TO APPROACH THESE KIND OF PROBLEMS
7
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?
8
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)?
9
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!$) ?
1 vote
10
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"); } } } }
11
If f(n) = O(g(n)) then is it always true g(n) = (f(n)) ??? please explain.
12
T(n) = 4T(n/2) + n2.$\sqrt{2}$ In thetha notation?
13
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?
14
15
16
Solve the following recurrence relation $T(n)=4T(n/2)+n^2 \sqrt 2$
17
f(n)=Ω(n),g(n)=O(n) than what is f(n).g(n)
18
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.)
19
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 )
20
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.
21
22
–1 vote
23
What will be the time complexity of a function f(n) = n^-2 i.e. pow (n,-2) ?
24
What is the time complexity of the following code snippet? Assume x is a global variable and “statement” takes O(n) time?
25
If F(n) = (log n)n then, is F(n) = O(n2) true? Also, what about F(n) = $\Theta$(n2)
26
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++; } } } }
1 vote