Dark Mode

Recent questions tagged time-complexity

1 vote

2 answers

241

Gate Applied Practice Test
Question--> The time required to find the 99th smallest element from a min heap of n elements is (given that we have access to the array elements)

lalitver10 asked in Programming in C Jan 13, 2022

1.1k views

0 votes

1 answer

242

Algorithms | Made Easy Full Syllabus Test
Consider two arrays A and B which are integer types. Array A has n distinct values in it and array B also has n distinct values in it, but A and B can share some values. What is the worst-case running time to compute A - ... complexity O(n). However, the given solution is : Is it always assumed that the algorithm should work without any auxiliary space?

palashbehra5 asked in Algorithms Jan 12, 2022

by palashbehra5

412 views

0 votes

2 answers

243

Made Easy Test Series
Which of the following can be the best algorithm(s) for all pair of the shortest path problem? I. ‘V’ invocations of Dijkstra algorithm ⇒ Ο(VE logV). II. ‘V’ invocations of Bellman-Ford algorithm ⇒ Ο(V2 E). III. ‘1’ invocations of Floyd-Warshall algorithm ⇒ Ο(V3).

LRU asked in Algorithms Jan 8, 2022

by LRU

374 views

1 vote

1 answer

244

Self doubts
T(n)=T(n/5)+T(7n/10)+an a: constant what will be the time complexity of the above recurrence relation?? Please share the approach for this kind of recurrence relation

lalitver10 asked in Algorithms Jan 4, 2022

598 views

0 votes

1 answer

245

#Made Easy Test Series
Find the time complexity of the given program

Nitesh_Yadav asked in Algorithms Jan 4, 2022

by Nitesh_Yadav

490 views

2 votes

1 answer

246

#self doubt
how to solve this?

samarpita asked in Algorithms Dec 29, 2021

653 views

1 vote

1 answer

247

NPTEL Assignment Question
What is the complexity of inorder traversal for a binary search tree with n nodes? O(log n) whether the tree is balanced or unbalanced. O(log n) if the tree is balanced, O(n) otherwise. O(n) whether the tree is balanced or unbalanced. O(n) if the tree is balanced, O(n log n) otherwise.

rsansiya111 asked in DS Dec 8, 2021

597 views

2 votes

1 answer

248

NPTEL Assignment Question
Suppose we do merge sort with a three-way split: divide the array into 3 equal parts, sort each part and do a 3 way merge. What would the worst-case complexity of this version be? O($n^2$) O($n^2$ log3n) O(n log2n) O(n $(log2n)^2$)

rsansiya111 asked in Algorithms Dec 8, 2021

843 views

0 votes

1 answer

249

NPTEL Assignment Question
Suppose we want to extend the union-find data structure to support the operation Reset(c), which takes as input the name of a component c and then breaks up c into singleton components, like MakeUnionFind(). For instance if c = 3 and c currently ... representation: O(n), Pointer representation: O(size(c)) Array representation: O(size(c)), Pointer representation: O(size(c))

rsansiya111 asked in Algorithms Dec 8, 2021

1.3k views

0 votes

3 answers

250

NPTEL Assignment Question
Suppose there are k sorted lists (decreasing order) with n/k elements in each list. What is the time complexity to merge them into one single sorted list. Hint: Maintain a heap of k elements. Think which k elements to choose. A. O(nlogk) B. O(n) C. O(nk) D. O(nlogn)

rsansiya111 asked in Algorithms Dec 8, 2021

722 views

0 votes

1 answer

251

NPTEL Assignment Question
. You are given a set of n points on the number line. They are given in arbitrary order. The task is to find the points that are closest to each other. To solve the problem you decide to take one point and compute its distance to all other points and repeat ... closest pair. What is the running time of this algorithm ? O(nlgn) O(n^2) Runtime is independent of n. O(log n)

rsansiya111 asked in Algorithms Dec 8, 2021

7.5k views

0 votes

1 answer

252

NPTEL Assignment Question

rsansiya111 asked in Algorithms Dec 7, 2021

304 views

0 votes

0 answers

253

NIELIT STA 2021
The time complexity of solving the Longest Common Subsequence problem using Dynamic Programming is: (m and n are lengths of subsequences) O(m.n) O(m+n) O(log m.n) O(m/n)

rsansiya111 asked in Algorithms Dec 6, 2021

310 views

0 votes

1 answer

254

#timecomplexity
We are having 4 sorted sub-lists of size n/4, What is the time complexity to merge them in a single sorted list?

Crackca asked in Algorithms Nov 20, 2021

313 views

3 votes

1 answer

255

Applied Gate Test Series
Consider the function given below ? Assume T(0) = 0 int fun( int n ) { if ( n <= 0 ) return 0; int i = random( n - 1 ); return fun(i) + fun(n - i - 1); } random(n) returns an integer in the range [0, n] in constant time What is the time complexity of the above function? $\Theta (n^{2})$ $\Theta (n)$ $\Theta (n\log n)$ None

Aashay kaurav asked in Algorithms Nov 16, 2021

by Aashay kaurav

520 views

2 votes

1 answer

256

Applied Test Series
The time required to determine the minimum element from the max heap of size O(log(n)) is given by

LRU asked in DS Nov 3, 2021

by LRU

827 views

1 vote

1 answer

257

Applied Test Series
What is the correct order ?

LRU asked in Algorithms Nov 2, 2021

by LRU

386 views

2 votes

2 answers

258

Applied Test Series
Consider an array contains n integers, each integer belongs to {0, 1, 2}. What is the best case time complexity to sort an array?

LRU asked in Algorithms Oct 15, 2021

by LRU

642 views

0 votes

2 answers

259

Sorting(Algorithms)
The complexity of comparison based sorting algorithm is (nlogn) .How?

_Madhuri asked in Algorithms Oct 9, 2021

646 views

1 vote

1 answer

260

Applied gate demo test
Consider the following function int foo(int n) { int p = 1 ; if (n && !(n&(n-1))) return n; while (p<n) { p <<= 1; } return p; } What is the worst case time complexity of function foo(n)

devilstephen7 asked in Algorithms Sep 20, 2021

by devilstephen7

511 views

0 votes

0 answers

261

#algorithms #databases
What is the worst-case time complexity to find attribute closure of a set of elements? i.e. Let find attribute closure for {AB}+ R(A,B,C,D,E,F,G,H,I,….. up to k time) { A → BC B → DE D → F F → GHI . . . and so on up to k functional dependencies... } My answer is O(k^k). Please verify someone.

Crackca asked in Algorithms Sep 6, 2021

152 views

2 votes

1 answer

262

TIFR CSE 2021 | Part B | Question: 15
Let $A\left [ i \right ] : i=0, 1, 2, \dots , n-1$ be an array of $n$ distinct integers. We wish to sort $A$ in ascending order. We are given that each element in the array is at a position that is at most $k$ away from its position in the sorted array, ... $t\left ( n \right ) = \Theta \left ( nk \right )$

soujanyareddy13 asked in Algorithms Mar 25, 2021

by soujanyareddy13

767 views

14 votes

4 answers

263

GATE CSE 2021 Set 2 | Question: 2
Let $H$ be a binary min-heap consisting of $n$ elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in $H$? $\Theta (1)$ $\Theta (\log n)$ $\Theta (n)$ $\Theta (n \log n)$

Arjun asked in DS Feb 18, 2021

by Arjun

8.7k views

14 votes

4 answers

264

GATE CSE 2021 Set 2 | Question: 8
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$? $\Theta ( \sqrt{n})$ $\Theta (\log _2(n))$ $\Theta(n^2)$ $\Theta(n)$

Arjun asked in Algorithms Feb 18, 2021

by Arjun

11.8k views

18 votes

3 answers

265

GATE CSE 2021 Set 1 | Question: 10
A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$? $\Theta(n\log n)$ $\Theta(n)$ $\Theta(\log n)$ $\Theta (1)$

Arjun asked in DS Feb 18, 2021

by Arjun

11.5k views

24 votes

7 answers

266

GATE CSE 2021 Set 1 | Question: 30
Consider the following recurrence relation. $T\left ( n \right )=\left\{\begin{array} {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.$ Which one of the following options is correct? $T(n)=\Theta (n^{5/2})$ $T(n)=\Theta (n\log n)$ $T(n)=\Theta (n)$ $T(n)=\Theta ((\log n)^{5/2})$

Arjun asked in Algorithms Feb 18, 2021

by Arjun

23.7k views

Page:

« prev
1
...
4
5
6
7
8
9
10
11
12
13
14
...
53
next »

Recent questions tagged time-complexity