search
Log In

Recent questions tagged asymptotic-notations

0 votes
1 answer
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
asked Sep 28, 2018 in Algorithms sushmita 128 views
0 votes
1 answer
2
Find the complexity of the following code fragment: int i = 1; for(; i <= n logn; i + +) { for(i + +; i <= n; i + +) { print(1) } }
asked Sep 28, 2018 in Algorithms sushmita 175 views
0 votes
4 answers
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.
asked Sep 28, 2018 in Algorithms mohitrai0_0 2k views
1 vote
2 answers
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; } }
asked Sep 28, 2018 in Algorithms sushmita 185 views
0 votes
2 answers
5
FIND THE TIME COMPLEXITY int i=1,j; for(;i <= n;i + +) { for(j = i; j <= nlogn; j∗ = 2) { sum + +; } }
asked Sep 28, 2018 in Algorithms sushmita 178 views
0 votes
1 answer
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}$
asked Sep 28, 2018 in Algorithms sushmita 257 views
0 votes
0 answers
7
State true/false f(n) != O(g(n)) and g(n) != O(f(n))
asked Sep 28, 2018 in Algorithms sushmita 83 views
0 votes
0 answers
8
0 votes
1 answer
9
f(n)=2(log2 n)2 , g(n)=log2n+1 How to give relation between them?.
asked Sep 22, 2018 in Algorithms Vishnathan 78 views
0 votes
1 answer
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.
asked Sep 21, 2018 in Algorithms balaganesh 101 views
0 votes
1 answer
11
0 votes
0 answers
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)
asked Sep 10, 2018 in Algorithms Devshree Dubey 104 views
0 votes
0 answers
14
How is Σ (1/k * log k) = O( n log n) for k=1 to n?
asked Sep 7, 2018 in Algorithms Nidhi Budhraja 66 views
0 votes
2 answers
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 !
asked Sep 5, 2018 in Algorithms balaganesh 138 views
0 votes
0 answers
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 .
asked Aug 22, 2018 in Algorithms Rishav Kumar Singh 193 views
0 votes
1 answer
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)
asked Aug 19, 2018 in Programming pradeepchaudhary 73 views
0 votes
1 answer
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?
asked Aug 15, 2018 in Algorithms Ayush Upadhyaya 192 views
0 votes
2 answers
19
Solution using back substitution method T(n) = 2T(n/2) + nlogn ? detailed solution please. ans is nlognlogn or n(logn)^2
asked Aug 10, 2018 in Algorithms manvi_agarwal 170 views
0 votes
3 answers
20
What is the time complexity of the following? for(i=0; i < n *n ; i = i *i) print("*");
asked Aug 9, 2018 in Algorithms smsubham 151 views
0 votes
1 answer
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.
asked Aug 6, 2018 in Algorithms Rahul Ranjan 1 255 views
1 vote
0 answers
22
Solve the recurrence relation $T(n) = T(\sqrt{n}) + n$
asked Jul 27, 2018 in Algorithms gauravkc 220 views
1 vote
1 answer
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;
asked Jul 26, 2018 in Algorithms Rishav Kumar Singh 115 views
2 votes
2 answers
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"); }
asked Jul 26, 2018 in Algorithms Rishav Kumar Singh 478 views
1 vote
1 answer
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()
asked Jul 25, 2018 in Algorithms Rishav Kumar Singh 210 views
1 vote
1 answer
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?
asked Jul 25, 2018 in Algorithms Rishav Kumar Singh 197 views
0 votes
0 answers
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
asked Jul 23, 2018 in Algorithms Swapnil Naik 117 views
0 votes
1 answer
28
1 vote
1 answer
29
which of the following estimates are true? Explain with valid reasons. a) (2n)! is theta (n)! b) log((2n)!) is theta (log(n)!)
asked Jul 14, 2018 in Algorithms AIkiran01 595 views
1 vote
0 answers
30
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.
asked Jul 14, 2018 in Algorithms Ayush Upadhyaya 202 views
...