Recent questions tagged time-complexity

Recent questions tagged time-complexity

0 votes

0 answers 32 views

#algorithms #timecomplexity
There a confusion about what should be the time complexity of the code... Involving modulo operator

Palash yadav asked in Algorithms Nov 12, 2021

by Palash yadav

135 points

32 views

0 votes

0 answers 103 views

Gate CSE 2012
The worst case running time to search for an element in a balanced binary search tree with n2^n elements is A. Theta (nlogn) B. Theta (n2^n) C. Theta (n) D. Theta (logn) I am confused about the term balanced here because though we know about AVL ... AVL tree here? And ofcourse I am also curious to know how to solve this question. I will be grateful for your opinions. Regards, Ananya

Ananya Nayak asked in DS Jul 3, 2021

by Ananya Nayak

5 points

103 views

0 votes

0 answers 61 views

Time and space complexity
There is an algorithm that took array of strings, sorted each string and then sorted the entire array.What would be the runtime?

SaileeDas asked in Algorithms Jun 28, 2021

5 points

61 views

0 votes

0 answers 24 views

#Algo_Coremen
In Master’s theorem T(n) = aT(n/b) + f(n), ‘a’ : Number of subproblems and ‘n/b’ : Size of the subproblem. Now, size of the subproblem can be expressed as ‘n/a’. Why do we need to use ‘b’?

Palash Nandi 1 asked in Algorithms Jun 23, 2021

by Palash Nandi 1

13 points

24 views

0 votes

1 answer 81 views

made easy question about time complexity
what is the time complexity in f( int n) { if(n <=2) return 1 else return f(floor(sqrt(n))) + n; }

pppankajsaini asked in Algorithms Apr 28, 2021

by pppankajsaini

9 points

81 views

1 vote

0 answers 28 views

#self doubt #Time complexity #tree
1) Time complexity to construct a Binary tree when inorder and preorder/postorder traversal of the tree is given. a) if inorder sorted b) if inorder is not sorted. 2) If construct Binary tree when pre-order and postorder to the tree is given. .....… My answer: 1 a) O( nlogn) 1 b) O(nlogn) 2) O(2^n) Please check and correct Thanks

Hradesh patel asked in Algorithms Feb 27, 2021

by Hradesh patel

9 points

28 views

1 vote

3 answers 1.0k views

GATE CSE 2021 Set 2 | Question: 2 | Video Solution

Arjun asked in DS Feb 18, 2021

by Arjun

1.4k points

1.0k views

0 votes

2 answers 1.0k views

GATE CSE 2021 Set 2 | Question: 8 | Video Solution

Arjun asked in Algorithms Feb 18, 2021

by Arjun

1.4k points

1.0k views

4 votes

3 answers 1.1k views

GATE CSE 2021 Set 1 | Question: 10 | Video Solution

Arjun asked in DS Feb 18, 2021

by Arjun

1.4k points

1.1k views

5 votes

5 answers 1.9k views

GATE CSE 2021 Set 1 | Question: 30 | Video Solution

Arjun asked in Algorithms Feb 18, 2021

by Arjun

1.4k points

1.9k views

0 votes

0 answers 34 views

Time Complexity
What is the time complexity of the following code? #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct{ char data; unsigned int freq; unsigned int parent, leftChild, rightChild; }HTNode, *HuffmanTree; typedef char** HuffmanCode; void ... HC; HuffmanTree HT; HuffmanCoding(HT, HC, word, c, len); PrintHuffmanCode(HC, word, c, len); return 0; }

byebey asked in Algorithms Feb 12, 2021

by byebey

5 points

34 views

0 votes

0 answers 68 views

GATE TIME COMPLEXITY
How to analyse the complexity for – for(i=2;i*i<=n;i++) like i know for i=2 it’ll run $\sqrt{n} $ times how to process further. sir zxy123, also which book i should refer for these as cormen or narsimha are not detailed for this topic.

donniedarko asked in Algorithms Jan 23, 2021

39 points

68 views

1 vote

1 answer 60 views

ace test series
Hi, This might be a easy problem for everyone...but can i get some help...which one is greater 6nlogn or 2^logn...

vipin.gautam1906 asked in Algorithms Jan 20, 2021

by vipin.gautam1906

9 points

60 views

0 votes

1 answer 54 views

Self doubt :Time Complexity -Iterative
Can Someone help me understand the time-complexity of dependent loops? for example, Q1> int i,j; for(i=1;i<n;i=i++) { for(j=1;j<=i;j=j*2) } Q2> int i,j; for(i=1;i<=n/2;i=i++) { for(j=1;j<=i;j++) }

donniedarko asked in Algorithms Jan 13, 2021

39 points

54 views

2 votes

0 answers 87 views

GateBook Full Length Test
Which of the following statements is/are true/correct ? A) Professor Ram gives a comparison-based sorting algorithm that runs in T(n) = 2T(n-1)+ 1. There is not enough information to know whether Ram's algorithm is correct. B) Professor ... base 6) so this also should not be the time complexity of a comparison based sorting algorithm. Can anyone confirm?.Thanks in advance

Deterministic asked in Algorithms Dec 28, 2020

by Deterministic

31 points

87 views

0 votes

1 answer 30 views

Applied Ai test series
What is worst case time complexity of Comparison based sorting? O(n) O(nlogn) O(n^2) none of the above

GATE2021_ayush asked in Algorithms Dec 21, 2020

by GATE2021_ayush

5 points

30 views

0 votes

1 answer 66 views

NIELIT NIC scientist-B 2020 set-C ques 56
Consider the algorithm that solves problems of size n by recursively solving two subproblems of size n-1 and then combining the solutions in constant time.Then the running time of the algorithm would be:- O(n) O(logn) O(nlogn) O($n^{2}$)

ayush.5 asked in Algorithms Nov 26, 2020

99 points

66 views

1 vote

1 answer 99 views

NIELIT STA 2018
Given an random unsorted array ‘A’ in which every element is at most ‘d’ distance from is position in sorted array where d<Size(A). If we applied the insertion sort over this array, then the time complexity of algorithm is: O($n\log d$) O($n^2\log d$) O($nd$) O($n^2d$)

Sudarshan Bandyopadh asked in Algorithms Nov 18, 2020

by Sudarshan Bandyopadh

17 points

99 views

1 vote

1 answer 58 views

Testbook Test series
What is the best case time complexity to find the smallest element in Max-heap implemented using array with n^3 * logn elements? Ω(logn) Ω(n) Ω(n^3logn) Ω(1)

rsamarth asked in Algorithms Nov 16, 2020

29 points

58 views

1 vote

1 answer 33 views

GATE1988-6 Time Complexity Algorithms
Can someone please explain what this function do with a diagram and what does it mean by payoff and INF and negate INF? https://gateoverflow.in/94363/gate1988-6i

Akshar Ganatra asked in Algorithms Nov 6, 2020

by Akshar Ganatra

9 points

33 views

0 votes

0 answers 20 views

Self_doubt, Code sample from Galvin:Implicit Threading (with few modifications)

Nikhil_dhama asked in Algorithms Aug 31, 2020

by Nikhil_dhama

227 points

20 views

0 votes

2 answers 100 views

Self doubt in the Kruskal Algorithm
Why in Kruskal’s Algorithm we use $\textbf{O(V+E)}$ and not $\mathbf{V*E}$ Since, in order to check cycle we use union-find algorithm whic in worst case takes $\textbf{O(V)}$? Can someone please explain this?

`JEET asked in Algorithms Aug 25, 2020

by `JEET

191 points

100 views

0 votes

1 answer 1.5k views

GeekForGeeks
Consider an array consisting of –ve and +ve numbers. What would be the worst case time complexity of an algorithm to segregate the numbers having same sign altogether i.e all +ve on one side and then all -ve on the other ? A) O(N) B) O(N Log N) C) O(N * N) D) O(N Log Log N)

Musa asked in DS Aug 21, 2020

by Musa

5 points

1.5k views

0 votes

1 answer 35 views

Algorithms (Time Complexity)
The outer loop is running O(log(n)) times and the inner loop is running O(n) times. The answer is given O(n). Will it be the same case if the time complexity of the inner loop is more than the outer loop? Please give a solution with complete analysis.

Mellophi asked in Algorithms Aug 9, 2020

363 points

35 views

0 votes

0 answers 64 views

Geekforgeeks Contest - Algorithms
Huffman coding is a lossless data compression algorithm. The most frequent character gets the smallest code and the least frequent character gets the largest code. Consider the following statements regarding Huffman coding algorithm? S1 : The time ... statements S1, S2, and S3 are correct. I am not getting proper explanation on Geekforgeeks for this question.

anurag_yo asked in Algorithms Aug 1, 2020

5 points

64 views

0 votes

1 answer 69 views

Self Doubt:Time Complexity
What is time complexity to find median of medians?

srestha asked in Algorithms Jun 30, 2020

1.0k points

69 views

0 votes

1 answer 48 views

Time complexity
#include <stdio.h> int main(void){ // Your code here! for(int i=1;i<=4;i++) { // printf("%d\n",i); for(int j=1; j<=i;j++) { printf("%s\n", "pankaj"); } printf("\n"); } } i think time complexity is n^2 ...is it right?

pppankajsaini asked in Programming Jun 19, 2020

by pppankajsaini

9 points

48 views

0 votes

1 answer 42 views

Time Complexity - Self Doubt Question

2207akash asked in Algorithms Jun 13, 2020

5 points

42 views

0 votes

1 answer 102 views

Self-Doubt CLRS
How does the partition algorithm has O(1) space complexity instead of O(N) if it modifies the input array itself even if it doesn't use any extra space?

nvs16 asked in Algorithms Jun 10, 2020

by nvs16

9 points

102 views

0 votes

2 answers 42 views

Time complexity of below program
what should be the time complexity of below program anyone can anyone please explain for(i=1;i<=n:++i) { for(i=1;i<=n^2:++i) { for(i=1;i<=n^3:++i) { x=y+z; } } }

Sumit goyal 2 asked in Programming May 23, 2020

by Sumit goyal 2

5 points

42 views

0 votes

0 answers 100 views

https://www.youtube.com/watch?time_continue=1&v=mZjkxOknmhU&feature=emb_logo

Deb Prakash asked in Algorithms May 7, 2020

5 points

100 views

0 votes

1 answer 70 views

Clrs book,mit Assignment
$T(n) =2^{n}T(n/2) +n^{n}$

Palash yadav asked in Algorithms May 5, 2020

by Palash yadav

135 points

70 views

1 vote

1 answer 51 views

Find time complexity of T(n) = 2*T(n-1) + 3*T(n-2)

roh asked in Algorithms Apr 23, 2020

by roh

9 points

51 views

0 votes

1 answer 45 views

Complexity analysis of algorithms
What is the time complexity of the below algorithm: sum = 0; for(i=0; i<=n; i++){ for(j=1; j<= i; j=j*2){ sum = sum + j } }

roh asked in Algorithms Apr 20, 2020

by roh

9 points

45 views

0 votes

1 answer 37 views

GATE2016-2-15 Video Solution
$N$ items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the ... together? $O(\log^{2} N)$ $O(N)$ $O(N^{2})$ $\Theta\left(N^{2}\log N\right)$

admin asked in DS Apr 18, 2020

by admin

585 points

37 views

0 votes

0 answers 21 views

GATE2007-15,ISRO2016-26 Video Solution
Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any $n > 0$ is: $\lceil \log_2n \rceil +1$ $n$ $\lceil \log_2n \rceil$ $\lfloor \log_2n \rfloor +1$

admin asked in Algorithms Apr 18, 2020

by admin

585 points

21 views

0 votes

0 answers 15 views

GATE2014-1-42 Video Solution
Consider the following pseudo code. What is the total number of multiplications to be performed? D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3 Half of the product of the $3$ consecutive integers. One-third of the product of the $3$ consecutive integers. One-sixth of the product of the $3$ consecutive integers. None of the above.

admin asked in Algorithms Apr 18, 2020

by admin

585 points

15 views

0 votes

0 answers 26 views

GATE2008-40 Video Solution
The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is $\Theta(n)$ $\Theta(\log n)$ $\Theta(\log^*n)$ $\Theta(1)$

admin asked in Algorithms Apr 18, 2020

by admin

585 points

26 views

0 votes

0 answers 26 views

GATE2003-66 Video Solution
The cube root of a natural number $n$ is defined as the largest natural number $m$ such that $(m^3 \leq n)$ . The complexity of computing the cube root of $n$ ($n$ is represented by binary notation) is $O(n)$ but not $O(n^{0.5})$ $O(n^{0.5})$ ... constant $m>0$ $O( (\log \log n)^k )$ for some constant $k > 0.5$, but not $O( (\log \log n)^{0.5} )$

admin asked in Algorithms Apr 18, 2020

by admin

585 points

26 views

0 votes

0 answers 19 views

GATE2007-45 Video Solution
What is the $\text{time complexity}$ of the following recursive function? int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor (sqrt(n))) + n); } $\Theta(n^2)$ $\Theta(n \log_2n)$ $\Theta(\log_2n)$ $\Theta(\log_2\log_2n)$

admin asked in Algorithms Apr 18, 2020

by admin

585 points

19 views

Page:

1
2
3
4
next »

Search GATE CSE Doubts