# Recent questions tagged asymptotic-notations

1
If both of the algorithms A and B need O(nlogn) time then they both are equally efficient and finish in same amount of time. TRUE OR FALSE
2
Find the complexity of the following code fragment: int i = 1; for(; i <= n logn; i + +) { for(i + +; i <= n; i + +) { print(1) } }
3
I was wondering whether the recurrence T(n) = T(n/2) + 2n could be solved by using master theorem, and what would be the way. I tried solving the recurrence but can't. There is no mention to it in CLRS book. Please help. Thanks in advance.
1 vote
4
Find the complexity of the following function when called with some integer n: void foo(n) { int i,j,k,x=0; for (i=1 ; i ≤ n ; i++) for (j=1 ; j ≤ i * i ; j++) { for ( k = 1 ; k ≤ j ; k++) { x=x+10; } }
5
FIND THE TIME COMPLEXITY int i=1,j; for(;i <= n;i + +) { for(j = i; j <= nlogn; j∗ = 2) { sum + +; } }
6
Arrange the following functions in their increasing order of complexities. $f(n) = n ^{0.999999} * logn$ ($log n$ is not in power) $g(n) = 10000 n$ $h(n) = n^{2}$ $k(n) = (1.000001)^{n}$ $p(n) =\large \frac{2 ^{√n}}{ n^{2}}$ $q(n) = \Large \frac{n^{1.000001}}{logn}$
7
State true/false f(n) != O(g(n)) and g(n) != O(f(n))
8
Why does (1/3+1/c) <=1?
9
f(n)=2(log2 n)2 , g(n)=log2n+1 How to give relation between them?.
10
for(i=0;i<n;i++) for(j=0;j<i;j++) for(k=0;k<j;k++) what is the time complexity of above psudo code? explain.
11
12
13
Please help with the following in Time Complexity. 1)Show that the following order-of-magnitude results hold: a)3n=O(n!) b)(n3 -2n)/(n+1)=theta(n2) c)n3 /log(n+1)=O(n3) but not O(n2) 2)What is wrong with the following argument? x=O(n4),y=O(n2),therefore x/y=O(n2). 3) What is wrong with ... with the following argument? f(n)=O(n2)+O(n), so that f(n)-g(n)=O(n2 )+O(n)-O(n2). Therefore, f(n)-g(n)=O(n)
14
How is Σ (1/k * log k) = O( n log n) for k=1 to n?
15
The running time of an algorithm is given by T(n)=T(n-1)+T(n-2)-T(n-3), ifn>3 =n, otherwise The order of this algorithm is a)n b)log n c)n^n d)n^2 explain !
16
I got this question from here https://gateoverflow.in/169286/time-complexity Is this Question Correct i have doubt . If correct please explain Which of the following statements is/are TRUE? $i)$ The time complexity of recurrence relation $A(n) = 3A(n/2)+n^{2}$is asymptotically ... $O( 7 ^ {n/53})$ is asymptotically faster But i am not able to get the answer because of question statement .
17
What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list? a) O(1) b) O(n) c) θ(n) d) θ(1)
18
Let $f(n)$ and $g(n)$ be asymptotically positive functions. Prove or disprove below fact (h) $f(n)+o(f(n))=\Theta(f(n))$ is it true?
19
Solution using back substitution method T(n) = 2T(n/2) + nlogn ? detailed solution please. ans is nlognlogn or n(logn)^2
20
What is the time complexity of the following? for(i=0; i < n *n ; i = i *i) print("*");
21
How can we apply Masters theorem to these equations : T(n) = 16*T(n/4) + n! and T(n) = 4*T(n/2) + cn Please explain the process.
1 vote
22
Solve the recurrence relation $T(n) = T(\sqrt{n}) + n$
1 vote
23
Analyze the runtime of the following piece of code. Give a bound using Θ notation. function Pesky(n) r ←0; for i ←1 to n do for j ←1 to i do for k ← j to i+j do r ←r + 1; return r;
24
What is the time complexity of following function fun()? Assume that log(x) returns log value in base 2. void fun() { int i, j; for (i=1; i<=n; i++) for (j=1; j<=log(i); j++) printf("GeeksforGeeks"); }
1 vote
25
Consider the following two functions. What are time complexities of the functions? int fun1(int n) { if (n <= 1) return n; return 2*fun1(n-1); } int fun2(int n) { if (n <= 1) return n; return fun2(n-1) + fun2(n-1); } (A) O(2^n) for both fun1() and fun2() (B) O(n) for fun1() and O(2^n) for fun2() (C) O(2^n) for fun1() and O(n) for fun2() (D) O(n) for both fun1() and fun2()
1 vote
26
In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort?
27
I didn't understand Big-O notation: This is CORMEN exercise problem - 3.1-2 Solution link: https://www.csee.umbc.edu/~nam1/TA/HWSols/hw1sol.pdf
What is the time complexity of the below code? for($k=n^{10};k \geq 5;k=k^{\frac{1}{7}},k=k^2$) { $k=k^5;$ $k=k-10$ } My answer comes to be $O(log_{\frac{7}{10}}log_5(n^{10}))$ Please verify.