Recent questions tagged time-complexity - GATE CSE Doubts

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 21 hours ago in Algorithms by Mellophi (159 points) | 10 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 in Algorithms by anurag_yo (7 points) | 4 views

0 votes

0 answers

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

asked May 7 in Algorithms by Deb Prakash (7 points) | 28 views

0 votes

0 answers

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

asked Apr 23 in Algorithms by roh (17 points) | 14 views

0 votes

0 answers

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 in Algorithms by roh (17 points) | 22 views

0 votes

0 answers

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 in DS by admin (3.6k points) | 3 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 in Algorithms by admin (3.6k points) | 2 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 in Algorithms by admin (3.6k points) | 4 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 in Algorithms by admin (3.6k points) | 6 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 in Algorithms by admin (3.6k points) | 3 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 in Algorithms by admin (3.6k points) | 3 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 in Algorithms by admin (3.6k points) | 2 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 in Algorithms by admin (3.6k points) | 2 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 in Algorithms by admin (3.6k points) | 4 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 in Algorithms by admin (3.6k points) | 4 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 in Algorithms by admin (3.6k points) | 3 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 in Algorithms by admin (3.6k points) | 3 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 in Algorithms by admin (3.6k points) | 1 view

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 in Algorithms by admin (3.6k points) | 3 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 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2004-83, ISRO2015-40 Video Solution
The time complexity of the following C function is (assume $n > 0$) int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); } $O(n)$ $O(n \log n)$ $O(n^2)$ $O(2^n)$

asked Apr 18 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2015-2-22 Video Solution
An unordered list contains $n$ distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is $\Theta(n \log n)$ $\Theta(n)$ $\Theta(\log n)$ $\Theta(1)$

asked Apr 18 in Algorithms by admin (3.6k points) | 4 views

0 votes

0 answers

GATE2008-74 Video Solution
Consider the following C functions: int f1 (int n) { if(n == 0 || n == 1) return n; else return (2 * f1(n-1) + 3 * f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 3; for(i = 2; ... $f2(n)$ are $\Theta(n)$ and $\Theta(n)$ $\Theta(2^n)$ and $\Theta(n)$ $\Theta(n)$ and $\Theta(2^n)$ $\Theta(2^n)$ and $\Theta(2^n)$

asked Apr 18 in Algorithms by admin (3.6k points) | 5 views

0 votes

0 answers

GATE2016-2-39 Video Solution
The given diagram shows the flowchart for a recursive function $A(n)$. Assume that all statements, except for the recursive calls, have $O(1)$ time complexity. If the worst case time complexity of this function is $O(n^{\alpha})$, then the least possible value (accurate up to two decimal positions) of $\alpha$ is ________. Flow chart for Recursive Function $A(n)$.

asked Apr 18 in Algorithms by admin (3.6k points) | 3 views

0 votes

0 answers

GATE1999-1.13 Video Solution
Suppose we want to arrange the $n$ numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is $n-1$ $n$ $n+1$ None of the above

asked Apr 18 in Algorithms by admin (3.6k points) | 4 views

0 votes

0 answers

GATE2003-22 Video Solution
The unusual $\Theta(n^2)$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running ... $\Theta(n^2)$ become $\Theta(n (\log n)^2)$ become $\Theta(n \log n)$ become $\Theta(n)$

asked Apr 18 in Algorithms by admin (3.6k points) | 4 views

0 votes

0 answers

GATE1992-01,ix Video Solution
Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is _______

asked Apr 18 in Algorithms by admin (3.6k points) | 5 views

0 votes

0 answers

GATE2001-1.14 Video Solution
Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using Randomized quicksort? $O(n)$ $O(n \log n)$ $O(n^2)$ $O(n!)$

asked Apr 18 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2007-51 Video Solution
Consider the following C program segment: int IsPrime (n) { int i, n; for (i=2; i<=sqrt(n);i++) if(n%i == 0) {printf("Not Prime \n"); return 0;} return 1; } Let $T(n)$ denote number of times the $for$ loop is executed by the program on input $n$. Which of the ... $T(n) = O(n) \: \text{ and } T(n) = \Omega(\sqrt{n})$ None of the above

asked Apr 18 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2003-35 Video Solution
Consider the following recurrence relation $T(1)=1$ $T(n+1) = T(n)+\lfloor \sqrt{n+1} \rfloor$ for all $n \geq 1$ The value of $T(m^2)$ for $m \geq 1$ is $\frac{m}{6}\left(21m-39\right)+4$ $\frac{m}{6}\left(4m^2-3m+5\right)$ $\frac{m}{2}\left(3m^{2.5}-11m+20\right)-5$ $\frac{m}{6}\left(5m^3-34m^2+137m-104\right)+\frac{5}{6}$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2016-2-13 Video Solution
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in the ascending order, which of the following are TRUE? Quicksort runs in $\Theta (n^2)$ time Bubblesort runs in $\Theta (n^2)$ time Mergesort runs in ... time Insertion sort runs in $\Theta (n)$ time I and II only I and III only II and IV only I and IV only

asked Apr 18 in Algorithms by admin (3.6k points) | 3 views

0 votes

0 answers

GATE2010-12 Video Solution
Two alternative packages $A$ and $B$ are available for processing a database having $10^k$ records. Package $A$ requires $0.0001 n^2$ time units and package $B$ requires $10n\log_{10} n$ time units to process $n$ records. What is the smallest value of $k$ for which package $B$ will be preferred over $A$? $12$ $10$ $6$ $5$

asked Apr 18 in Algorithms by admin (3.6k points) | 3 views

0 votes

0 answers

GATE2001-1.16 Video Solution
Let $f(n) = n^2 \log n$ and $g(n) = n(\log n)^{10}$ be two positive functions of $n$. Which of the following statements is correct? $f(n) = O(g(n)) \text{ and } g(n) \neq O(f(n))$ $g(n) = O(f(n)) \text{ and } f(n) \neq O(g(n))$ $f(n) \neq O(g(n)) \text{ and } g(n) \neq O(f(n))$ $f(n) =O(g(n)) \text{ and } g(n) = O(f(n))$

asked Apr 18 in Algorithms by admin (3.6k points) | 3 views

0 votes

0 answers

GATE2004-39 Video Solution
Two matrices $M_1$ and $M_2$ are to be stored in arrays $A$ and $B$ ... column-major order best if both are in row-major order best if both are in column-major order independent of the storage scheme

asked Apr 18 in Algorithms by admin (3.6k points) | 3 views

0 votes

0 answers

GATE2000-1.15 Video Solution
Let $S$ be a sorted array of $n$ integers. Let $T(n)$ denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than $1000$ in $S$. Which of the following statement is true? $T (n)$ is $O(1)$ $n \leq T(n) \leq n \log_2 n$ $n \log_2 n ≤ T(n) < \frac{n}{2}$ $T(n) = \left (\frac{n}{2} \right)$

asked Apr 18 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2007-IT-17 Video Solution
Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute $b^n \bmod{m}, 0 \leq b, n \leq m$ ? $O(\log n)$ $O(\sqrt n)$ $O\Biggl (\frac{n}{\log n} \Biggr )$ $O(n)$

asked Apr 18 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2008-7 Video Solution
The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity $\Theta(n)$ $\Theta(m)$ $\Theta(m+n)$ $\Theta(mn)$

asked Apr 18 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2009-35 Video Solution
The running time of an algorithm is represented by the following recurrence relation: $T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$ Which one of the following represents the time complexity of the algorithm? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$

asked Apr 18 in Algorithms by admin (3.6k points) | 3 views

0 votes

0 answers

GATE1999-11a Video Solution
Consider the following algorithms. Assume, procedure $A$ and procedure $B$ take $O (1)$ and $O(1/n)$ unit of time respectively. Derive the time complexity of the algorithm in $O$-notation. algorithm what (n) begin if n = 1 then call A else begin what (n-1); call B(n) end end.

asked Apr 18 in Algorithms by admin (3.6k points) | 5 views

0 votes

0 answers

GATE1999-1.16 Video Solution
If $n$ is a power of $2$, then the minimum number of multiplications needed to compute $a^n$ is $\log_2 n$ $\sqrt n$ $n-1$ $n$

asked Apr 18 in Algorithms by admin (3.6k points) | 2 views

Page:

1
2
3
next »

7,751 questions

1,853 answers

11,220 comments

95,105 users