Recent questions tagged time-complexity - GATE CSE Doubts

+1 vote

0 answers

#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

asked Feb 27 in Algorithms by Hradesh patel (9 points) | 16 views

0 votes

0 answers

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

asked Feb 12 in Algorithms by byebey (5 points) | 21 views

0 votes

0 answers

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.

asked Jan 23 in Algorithms by donniedarko (39 points) | 35 views

+1 vote

1 answer

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

asked Jan 20 in Algorithms by vipin.gautam1906 (9 points) | 40 views

0 votes

1 answer

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

asked Jan 13 in Algorithms by donniedarko (39 points) | 24 views

+2 votes

0 answers

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

asked Dec 28, 2020 in Algorithms by Deterministic (31 points) | 45 views

0 votes

1 answer

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

asked Dec 21, 2020 in Algorithms by GATE2021_ayush (5 points) | 24 views

0 votes

1 answer

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

asked Nov 26, 2020 in Algorithms by ayush.5 (99 points) | 18 views

+1 vote

1 answer

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

asked Nov 18, 2020 in Algorithms by Sudarshan Bandyopadh (11 points) | 43 views

+1 vote

1 answer

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)

asked Nov 16, 2020 in Algorithms by rsamarth (29 points) | 47 views

+1 vote

1 answer

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

asked Nov 6, 2020 in Algorithms by Akshar Ganatra (9 points) | 18 views

0 votes

0 answers

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

asked Aug 31, 2020 in Algorithms by Nikhil_dhama (151 points) | 13 views

0 votes

2 answers

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?

asked Aug 25, 2020 in Algorithms by `JEET (187 points) | 46 views

0 votes

1 answer

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)

asked Aug 21, 2020 in DS by Musa (5 points) | 93 views

0 votes

1 answer

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.

asked Aug 9, 2020 in Algorithms by Mellophi (363 points) | 21 views

0 votes

0 answers

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.

asked Aug 1, 2020 in Algorithms by anurag_yo (5 points) | 25 views

0 votes

1 answer

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

asked Jun 30, 2020 in Algorithms by srestha (1k points) | 52 views

0 votes

1 answer

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?

asked Jun 19, 2020 in Programming by pppankajsaini (9 points) | 39 views

0 votes

1 answer

Time Complexity - Self Doubt Question

asked Jun 13, 2020 in Algorithms by 2207akash (5 points) | 28 views

0 votes

1 answer

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?

asked Jun 10, 2020 in Algorithms by nvs16 (9 points) | 16 views

0 votes

2 answers

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

asked May 23, 2020 in Programming by Sumit goyal 2 (5 points) | 21 views

0 votes

0 answers

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

asked May 7, 2020 in Algorithms by Deb Prakash (5 points) | 53 views

0 votes

1 answer

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

asked May 5, 2020 in Algorithms by Palash yadav (9 points) | 54 views

+1 vote

1 answer

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

asked Apr 23, 2020 in Algorithms by roh (9 points) | 39 views

0 votes

1 answer

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

asked Apr 20, 2020 in Algorithms by roh (9 points) | 36 views

0 votes

1 answer

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

asked Apr 18, 2020 in DS by admin (573 points) | 23 views

0 votes

0 answers

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$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 10 views

0 votes

0 answers

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.

asked Apr 18, 2020 in Algorithms by admin (573 points) | 8 views

0 votes

0 answers

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

asked Apr 18, 2020 in Algorithms by admin (573 points) | 11 views

0 votes

0 answers

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

asked Apr 18, 2020 in Algorithms by admin (573 points) | 16 views

0 votes

0 answers

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

asked Apr 18, 2020 in Algorithms by admin (573 points) | 8 views

0 votes

0 answers

GATE2015-1-40 Video Solution
An algorithm performs $(\log N)^{\frac{1}{2}}$ find operations , $N$ insert operations, $(\log N)^{\frac{1}{2}}$ delete operations, and $(\log N)^{\frac{1}{2}}$ decrease-key operations on a set of data items ... if the goal is to achieve the best total asymptotic complexity considering all the operations? Unsorted array Min - heap Sorted array Sorted doubly linked list

asked Apr 18, 2020 in Algorithms by admin (573 points) | 11 views

0 votes

0 answers

GATE2007-44 Video Solution
In the following C function, let $n \geq m$. int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function? $\Theta(\log_2n)$ $\Omega(n)$ $\Theta(\log_2\log_2n)$ $\Theta(\sqrt{n})$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 5 views

0 votes

0 answers

GATE2004-82 Video Solution
Let $A[1,\ldots,n]$ be an array storing a bit ($1$ or $0$) at each location, and $f(m)$ is a function whose time complexity is $\Theta(m)$. Consider the following program fragment written in a C like language: counter = 0; for (i=1; i<=n; i++) { if a[i ... The complexity of this program fragment is $\Omega(n^2)$ $\Omega (n\log n) \text{ and } O(n^2)$ $\Theta(n)$ $o(n)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 10 views

0 votes

0 answers

GATE2006-54 Video Solution
Given two arrays of numbers $a_{1},...,a_{n}$ and $b_{1},...,b_{n}$ where each number is $0$ or $1$, the fastest algorithm to find the largest span $(i, j)$ such that $ a_{i}+a_{i+1}+\dots+a_{j}=b_{i}+b_{i+1}+\dots+b_{j}$ or ... time in the key comparison mode Takes $\Theta (n)$ time and space Takes $O(\sqrt n)$ time only if the sum of the $2n$ elements is an even number

asked Apr 18, 2020 in Algorithms by admin (573 points) | 8 views

0 votes

0 answers

GATE2007-50 Video Solution
An array of $n$ numbers is given, where $n$ is an even number. The maximum as well as the minimum of these $n$ numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed? At least $2n-c$ comparisons, for some ... $c$ are needed. At most $1.5n-2$ comparisons are needed. At least $n\log_2 n$ comparisons are needed None of the above

asked Apr 18, 2020 in Algorithms by admin (573 points) | 7 views

0 votes

0 answers

GATE2019-37 Video Solution
There are $n$ unsorted arrays: $A_1, A_2, \dots, A_n$. Assume that $n$ is odd.Each of $A_1, A_2, \dots, A_n$ contains $n$ distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of $A_1, A_2, \dots , A_n$ is $O(n)$ $O(n \: \log \: n)$ $O(n^2)$ $\Omega (n^2 \log n)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 9 views

0 votes

0 answers

GATE2008-47 Video Solution
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. The total time required for this is $\Theta(\log n)$ $\Theta(n)$ $\Theta(n\log n)$ $\Theta(n^2)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 7 views

0 votes

0 answers

GATE2006-15 Video Solution
Consider the following C-program fragment in which $i$, $j$ and $n$ are integer variables. for( i = n, j = 0; i > 0; i /= 2, j +=i ); Let $val(j)$ denote the value stored in the variable $j$ after termination of the for loop. Which one of the following is true? $val(j)=\Theta(\log n)$ $val(j)=\Theta (\sqrt{n})$ $val(j)=\Theta( n)$ $val(j)=\Theta (n\log n)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 15 views

0 votes

0 answers

GATE2017-2-38 Video Solution
Consider the following C function int fun(int n) { int i, j; for(i=1; i<=n; i++) { for (j=1; j<n; j+=i) { printf("%d %d", i, j); } } } Time complexity of $fun$ in terms of $\Theta$ notation is $\Theta(n \sqrt{n})$ $\Theta(n^2)$ $\Theta(n \: \log n)$ $\Theta(n^2 \log n)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 6 views

Page:

1
2
3
4
next »

9,197 questions

3,182 answers

14,686 comments

96,162 users