Recent questions tagged time-complexity - GATE CSE Doubts

0 votes

0 answers

Applied Gate Test series
Find the time complexity of codes below – for(i=1;i<n*n*n*;i*=n) { for(j=0;j<n;j+=2) { for(k=1;k<n;k*=3) { //constant; } } } for(i=0;i<n;i++) { if(i mod 2 ==0) { for(j=i;j<n;j++) { if(i%2==0 && j%2==0) printf("Gate 2020"); } } }

asked Nov 3 in Algorithms by MRINMOY_HALDER (34 points) | 31 views

0 votes

0 answers

TIme complexity Made easy
What is time complexity for this function?

asked Oct 17 in Algorithms by vupadhayayx86 (6 points) | 19 views

0 votes

0 answers

geekforgeeks
int a = 0; for (i = 0; i < N; i++) { for (j = N; j > i; j--) { a = a + i + j; } } my doubt is an inner loop (J) is depend on i variable which is run n times. now how to evaluate the inner loop. please explain in details how TC is calculated.

asked Oct 10 in Algorithms by Hira Thakur (8 points) | 9 views

0 votes

1 answer

MadeEasy Workbook, DRDO 2008
Consider a sequence A of length n which is sorted except for one item that appears out of order.Which of the following can sort the sequence in O(n) time? (a) Heap sort (b) Quick sort (c) Merge sort (d) Insertion sort

asked Oct 9 in Algorithms by Ansaaa24 (8 points) | 24 views

0 votes

2 answers

made easy test series quick sort time complexity

asked Sep 20 in Algorithms by ck (10 points) | 15 views

0 votes

0 answers

Made easy Test Series question....
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 by `JEET (157 points) | 9 views

0 votes

2 answers

Made easy test series question.
For the below message number of bits required in Huffman Coding is: abbaabccdabcd

asked Sep 11 in Algorithms by `JEET (157 points) | 23 views

0 votes

1 answer

Made easy test series.
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 by `JEET (157 points) | 17 views

0 votes

0 answers

Made Easy online test series
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 by `JEET (157 points) | 9 views

0 votes

2 answers

what does tightest lower bound means??
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 by Rishav_Bhatt (8 points) | 30 views

0 votes

3 answers

Algorithms - Time Complexity analysis
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 ... 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 by sagar2405 (87 points) | 45 views

0 votes

0 answers

Algorithms - Time complexity
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 by sagar2405 (87 points) | 15 views

0 votes

0 answers

Algorithms: Asymptotic Analysis
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 by Sambhrant Maurya (277 points) | 13 views

+1 vote

1 answer

Asymptotic Analysis
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 by Sambhrant Maurya (277 points) | 33 views

+1 vote

0 answers

How to solve this recurrence relation?
T(n)=T(k)+T(n−k−1)+θ(n) Can someone explain how to solve this?

asked Jul 30 in Algorithms by iarnav (71 points) | 14 views

0 votes

0 answers

cs501 Advance Computer Architecture TOPIC NAME: •Hard Disk Transfer Time Calculation

asked Jul 25 in CO & Architecture by Unaiza fatima (6 points) | 5 views

0 votes

1 answer

Self Doubt; Algorithms
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 ... 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 by Sambhrant Maurya (277 points) | 17 views

+1 vote

1 answer

Self Doubt: Algorithms
If n is a multiple of 3, then the minimum number of multiplications needed to calculate $a^{n}$ is?

asked Jul 19 in Algorithms by Sambhrant Maurya (277 points) | 16 views

+1 vote

2 answers

Time Complexity analysis
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 by Sambhrant Maurya (277 points) | 31 views

0 votes

2 answers

MadeEasy WorkBook Recurrence Relation
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 ... 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 by AliH (10 points) | 20 views

+1 vote

3 answers

Algorithms self doubt
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 by Sambhrant Maurya (277 points) | 20 views

To see more, click for the full list of questions or popular tags.

1,942 questions

1,184 answers

5,508 comments

89,631 users