search
Log In
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Sep 2019
  1. Satbir

    567 Points

  2. Bikram

    566 Points

  3. GAITONDE

    348 Points

  4. Vimal Patel

    87 Points

  5. Shaik Masthan

    38 Points

  6. BLACK_CLOUD

    14 Points

  7. sekhar_1621

    13 Points

  8. OgbeborBeatrice

    13 Points

  9. RAMYA.F

    9 Points

  10. vkw1111

    9 Points

Recent questions tagged time-complexity

0 votes
2 answers 7 views
0 votes
0 answers 4 views
Consider th following cases for quick sort to sort an array of n element $a[0...n-1]$ i) Choosing the pivot element randomly from the given array ii) choosing median element as pivot. Iii) Choosing middle element as pivot For which of the above cases quick sort always gives $O(nlogn)$ time complexity?
asked Sep 11 in Algorithms `JEET 144 points 4 views
0 votes
2 answers 17 views
For the below message number of bits required in Huffman Coding is: abbaabccdabcd
asked Sep 11 in Algorithms `JEET 144 points 17 views
0 votes
1 answer 9 views
Let $g(n) = \Omega(n)$, $f(n) = O(n)$ and $h(n) = \theta(n)$ then what is the time complexity of $[g(n) f(n) + h(n)]$ How to solve such questions?
asked Sep 11 in Algorithms `JEET 144 points 9 views
0 votes
0 answers 2 views
Consider an array A of length n, array contain number between (1 – 10), in any arbitary order, best sorting algorithm takes $650$ ns if $n = 50$, the time required by algorithm if n = 300.
asked Sep 11 in Algorithms `JEET 144 points 2 views
0 votes
2 answers 26 views
Here the tightest lower bound means?. (Please suggest some source if possible for such questions) https://gateoverflow.in/1026/gate2004-29
asked Aug 26 in Algorithms Rishav_Bhatt 8 points 26 views
0 votes
3 answers 39 views
1 .Let P be the problem. Suppose that the worst case asymptotic running time complexity of P is in O($n^2$lgn) and is also in Ω(n). Now let A be an algorithm that solves P. Which of the following is correct about A: A has worst-case time comlexity in O(lgn) A has ... . The best case time case complexity of an algorithm is θ(n). The Algorithm executes in time T(n) = Ω($n^2$) for every input data.
asked Aug 22 in Algorithms sagar2405 87 points 39 views
0 votes
0 answers 11 views
1 .Solve the recurrence: $T(n) = 2T(\sqrt n) + log\ n$ $T(n) = T(\frac{n}{2}) + 2T(\frac{n}{4}) +n$ 2 .$f(n) = n^{1.01}$ and $g(n) = n(log\ n)^2$ then which one is true $f(n) = O(g(n))$ $f(n) = \Omega(g(n))$ $f(n) = \Theta(g(n))$ 3 . $f(n) = n^{\frac{1}{2}}, g(n) = 1$, then is it correct $g(n) = o(fn)$ {$o$ = small o Not big $O$} Please solve the above questions.
asked Aug 22 in Algorithms sagar2405 87 points 11 views
0 votes
0 answers 8 views
The decreasing asymptotic order of the functions: F1:$2^{2^{n+1}}$ F2: log*log n F3: log log* n F4: (log n)! F5: $n^{log log n}$ F1,F5,F4,F2,F3 F1,F4,F5,F3,F2 F1,F5,F4,F2,F3 None of these
asked Aug 5 in Algorithms Sambhrant Maurya 204 points 8 views
1 vote
1 answer 25 views
Consider the following functions: $f(n)=\Omega(n^{3}) $ $g(n)=O(n^{2})$ $h(n)=\Theta (n^{2})$ Which one of the following is the correct asymptotic representation of f(n) + g(n) * h(n) ? $\Omega (n^{3})$ O($n^{4}$) $\Theta (n^{3})$ $\Omega (n^{4})$
asked Aug 4 in Algorithms Sambhrant Maurya 204 points 25 views
1 vote
0 answers 10 views
T(n)=T(k)+T(n−k−1)+θ(n) Can someone explain how to solve this?
asked Jul 30 in Algorithms iarnav 56 points 10 views
0 votes
0 answers 2 views
Consider a disk drive rotating at 20,000 rpm and a transfer rate of 80 MB/sec. The disk head consumes 4 milliseconds on average to reach the target sector from/to where to read/write the data. If we assume disk controller overhead is 0.5 milliseconds, what will be time required to read a block of 2 MB from the disk
asked Jul 25 in CO & Architecture Unaiza fatima 6 points 2 views
0 votes
1 answer 14 views
A programmer wants to create a dynamic array implementation of stack in which always a new array of size n+10 is created every time the array cannot accommodate more elements. For example, for inserting the first element, array of size 0+10=10 will be created. After inserting 10 elements ... to this new array. What is the time complexity of this stack implementation? O(n) O(log n) O(nlog n) O(1)
asked Jul 20 in Algorithms Sambhrant Maurya 204 points 14 views
1 vote
1 answer 12 views
If n is a multiple of 3, then the minimum number of multiplications needed to calculate $a^{n}$ is?
asked Jul 19 in Algorithms Sambhrant Maurya 204 points 12 views
1 vote
2 answers 28 views
What is the time complexity of the following code: for(i=1 to n) { for(j=1 to n) { for(k=j+1 to n) printf(“Something”); } }
asked Jul 17 in Algorithms Sambhrant Maurya 204 points 28 views
0 votes
2 answers 14 views
Consider the following function f void f(int n) { if(n <= 0 ) return; else { print(n); f(n-2); print(n); f(n-1); } } Let R(n) be recurrence relation which computes sum of values printed by f(n). Then R(n) is? R(n-1) + R(n-2) R(n-1) + R(n-2) + n R(n-1) + R(n-2) + 2n None of these For F(n) it’s time complexity should by T(n) = T(n-1) + T(n-2) + c I am not able to think what is happening with R(n).
asked Jul 17 in Algorithms AliH 10 points 14 views
1 vote
3 answers 16 views
If $f(n)=\sqrt{n}$ $g(n)=n^{1+\sin n}$ Then: f(n) = O g(n) f(n) = Ω g(n) f(n) = Θ g(n) f(n) and g(n) cannot be asymptotically compared
asked Jul 17 in Algorithms Sambhrant Maurya 204 points 16 views
To see more, click for the full list of questions or popular tags.
...