Recent questions tagged time-complexity

0 votes

2 answers 7 views

made easy test series quick sort time complexity

asked 1 day ago in Algorithms ck 6 points 7 views

0 votes

0 answers 4 views

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?

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

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

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

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?

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

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.

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

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

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

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.

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

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.

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

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

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

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})$

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

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

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

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

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

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)

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

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

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

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”); } }

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

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).

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

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

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

Log In

Register

Recent questions tagged time-complexity