search
Log In

Recent questions tagged asymptotic-notations

0 votes
2 answers
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?
asked Mar 19, 2019 in Algorithms Tanuj Guha Thakurta 151 views
1 vote
1 answer
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 ?
asked Mar 7, 2019 in Algorithms Ashish Roy 1 110 views
0 votes
1 answer
3
I am unable to Find its time complexity using Iterative method… Will any one help me out with this . Thank you :)
asked Jan 18, 2019 in Algorithms Nandkishor3939 177 views
0 votes
0 answers
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.
asked Jan 13, 2019 in Algorithms debanjan sarkar 95 views
1 vote
0 answers
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)
asked Jan 12, 2019 in Algorithms bts1jimin 152 views
0 votes
1 answer
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?
asked Jan 10, 2019 in Algorithms snaily16 109 views
0 votes
0 answers
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?
asked Jan 6, 2019 in Algorithms Markzuck 157 views
0 votes
0 answers
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})$
asked Jan 4, 2019 in Algorithms shreyansh jain 218 views
0 votes
0 answers
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
asked Jan 4, 2019 in Algorithms amit166 60 views
0 votes
1 answer
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)
asked Jan 4, 2019 in Algorithms saptarshiDey 721 views
0 votes
0 answers
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?
asked Dec 29, 2018 in Algorithms Markzuck 239 views
7 votes
1 answer
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)$
asked Dec 27, 2018 in Algorithms Ruturaj Mohanty 416 views
1 vote
0 answers
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)$
asked Dec 27, 2018 in Algorithms Shubhgupta 184 views
0 votes
1 answer
15
What is difference between tightest upper bound and tightest lower bound? Give ur explanation with examples?
asked Dec 26, 2018 in Algorithms Deepesh Pai 67 views
0 votes
1 answer
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?
asked Dec 23, 2018 in Algorithms sripo 192 views
3 votes
2 answers
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})$
asked Dec 18, 2018 in Algorithms Arjun 786 views
0 votes
1 answer
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)
asked Dec 11, 2018 in Algorithms Shivam Kasat 114 views
1 vote
3 answers
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$
asked Dec 7, 2018 in Algorithms Gupta731 189 views
0 votes
1 answer
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.
asked Dec 7, 2018 in Algorithms Gupta731 161 views
0 votes
1 answer
22
f(n) + O(f(n)) = Θ(f(n)) True or not? Explain please
asked Nov 18, 2018 in Algorithms Vegeta 66 views
0 votes
0 answers
23
How to solve the following recurrence relation? T(n) = T(n-6) + n2 , n>7 T(n) = 1 , n<= 7
asked Nov 17, 2018 in Algorithms garvit_vijai 134 views
4 votes
0 answers
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?
asked Nov 14, 2018 in Algorithms Ayush Upadhyaya 133 views
0 votes
1 answer
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$
asked Nov 13, 2018 in Algorithms Shubham Aggarwal 251 views
1 vote
0 answers
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.
asked Nov 6, 2018 in Algorithms sripo 500 views
1 vote
1 answer
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)))$
asked Nov 1, 2018 in Algorithms Lakshman Patel RJIT 128 views
1 vote
2 answers
28
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
asked Nov 1, 2018 in Algorithms Lakshman Patel RJIT 208 views
0 votes
0 answers
29
√logx = O(loglogx) is it true or false? and explain why?
asked Oct 29, 2018 in Algorithms suneetha 73 views
1 vote
1 answer
30
how to compute time complexity of this kind of recurrence relation- T(n)=T(n/2)+T(n/4)+T(n/8)+n
asked Oct 27, 2018 in Algorithms aditi19 208 views
...