# Recent questions tagged asymptotic-notations

1
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?
1 vote
2
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 ?
3
I am unable to Find its time complexity using Iterative method… Will any one help me out with this . Thank you :)
4
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.
1 vote
5
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)
6
7
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?
8
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?
9
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})$
10
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
11
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)
12
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?
13
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 terms of Big $\Theta$ notation for the function call to procedure A? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n \log \log n)$ $\Theta(n^2 \log n)$
1 vote
14
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)$
15
What is difference between tightest upper bound and tightest lower bound? Give ur explanation with examples?
16
Which of the below given sorting techniques has highest best-case runtime complexity. (A) Quick sort (B) Selection sort (C) Insertion sort (D) Bubble sort Answer: (B) Explanation: Quick sort best case time complexity is Ο(n logn) Selection sort best case time ... 2017-question-12/ I did not understand this as best case time should be O(n) sorting method what does highest best cases mean?
17
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! = \Omega(n^n) \text{ and } n! = \mathcal{O}(n^{n+\frac{1}{2}})$ ... $n! =\Theta((\frac{n}{e})^{n+\frac{1}{2}})$ $n! =\Theta(n^{n+\frac{1}{2}}2^{-n})$
18
a , c , d all three are right answer please explain if i am wrong.
19
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)
1 vote
20
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$
21
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.
22
f(n) + O(f(n)) = Θ(f(n)) True or not? Explain please
23
How to solve the following recurrence relation? T(n) = T(n-6) + n2 , n>7 T(n) = 1 , n<= 7
24
Which of the following is the correct order if they are ordered by asymptotic growth rates? $F_1:n^{lg\,lgn}$ $F_2:(3/2)^n$ $F_3:(lg\,n)^{lg\, n}$ $F_4:n!$ $F_3$ can be re-written as $n^{lg\,lgn}$ using property $a^{log_bc}=c^{log_ba}$ So, $F_4 \gt F_2 \gt F_1=F_3$ Is my order correct?
25
Which of the following functions given by their recurrences grows the fastest asymptotically? $T(n) = 8T(n/4) + 100n^2$ $T(n) = 81T(n/9) + 10n^2$ $T(n) = 16T(n/4)+ 100(n \log n)^{1.99}$ $T(n) = 100T(n/100)+ n \log^2 n$
1 vote
26
What is the time complexity for infinite loops Question 1 what is T(n) for this case While(1) { a=a+b; } Question 2 for this case if(1) { for i to n a=a+b } else { for i to n for j to n a=a+b } Edit 2: Compiled the code never goes to the else part ... %d",a,b); return 0; } output I get is 8 6 which means the else case is never executed hence in worst case do we have to consider the else part.
1 vote
27
Identify the FALSE statement: $A)$ $f(n)=\theta(f(\frac{n}{2})$ $implies$ $f(n^{2})=\theta(f(\frac{n^{2}}{2}))$ $B)$ $f(n)=O(g(n))$ $implies$ $log(f(n))=O(log(g(n)))$ where $n\geq2$ $C)$ $f(n)=O(g(n))$ $implies$ $2^{f(n)}=O(2^{g(n)})$ $D)$ $f(n)+g(n)=\theta(Max(f(n),g(n)))$
1 vote
Consider the following statements: $(1)$ Any two functions $f,g$ are always comparable under big Oh,that is $f=O(g)$ or $g=O(f)$ $(2)$ If $f=O(g)$ and $f=O(h)$ then $g(n)=\theta(h)$ $A)$ $(1)$ is true $(2)$ is false $B)$ $(1)$ is false $(2)$ is true $C)$ Both are false $D)$ Both are true