Recent questions tagged time-complexity / GATE Overflow for GATE CSE

5 votes

1 answer

271

GATE Overflow Test Series | Mock GATE | Test 4 | Question: 17
Consider a selection sorting implementation which takes $8$ time units for input of size $8$. How much time units will it take for an input of size $32?$

Consider a selection sorting implementation which takes $8$ time units for input of size $8$. How much time units will it take for an input of size $32?$

gatecse

310 views

gatecse asked Feb 1, 2021

4 votes

2 answers

272

GATE Overflow Test Series | Mock GATE | Test 4 | Question: 38
Consider the following C function. int func(int n) { int i, j, k, p, q=1; for(i=1 ; i<= n;i=i+1) { p=0; for(k=1 ; k <= n ; k=k+2) p++; for(j=n ; j>= 1 ; j=j/2) q=q*2; } return q; } Which one of the ... is the approximate value return by the above function? $\Theta(n^2)$ $\Theta(n^n)$ $\Theta(2^{n^2})$ $\Theta(2^{n\log \log n)}$

Consider the following C function.int func(int n) { int i, j, k, p, q=1; for(i=1 ; i<= n;i=i+1) { p=0; for(k=1 ; k <= n ; k=k+2) p++; for(j=n ; j>= 1 ; j=j/2) q=q*2; } re...

gatecse

419 views

gatecse asked Feb 1, 2021

4 votes

1 answer

273

GATE Overflow Test Series | Mock GATE | Test 4 | Question: 45
What is time complexity of Dijkstra's algorithm if we use sorted linked list instead of min-heap or priority queue. Assume graph $G(V,E)$ is represented by an adjacency list and $|V| = v$ and $|E| = e.$ $\Theta((v + e)\log v)$ $\Theta(v^2 + e \log v)$ $\Theta(v . e)$ $\Theta(v^2)$

What is time complexity of Dijkstra's algorithm if we use sorted linked list instead of min-heap or priority queue. Assume graph $G(V,E)$ is represented by an adjacency l...

gatecse

459 views

gatecse asked Feb 1, 2021

2 votes

1 answer

274

GATE Overflow Test Series | Mock GATE | Test 4 | Question: 48
A contractor has to get completed a task of $w$ units. He assigns Mr. $X$ for this work. Further Mr. $X$ divides this work into $3$ people because a person takes responsibility to do the work only if it is a single unit of work, otherwise, he divides the work ... $\Theta(w\log(w))$ $\Theta(2^{2 \log(w)} \log^2(w))$

A contractor has to get completed a task of $w$ units. He assigns Mr. $X$ for this work. Further Mr. $X$ divides this work into $3$ people because a person takes responsi...

gatecse

318 views

gatecse asked Feb 1, 2021

1 votes

1 answer

275

NIELIT Scientist B 2020 November: 100
Consider the algorithm that solves problems of size $n$ by recursively solving two sub problems of size $n-1$ and then combining the solutions in constant time. Then the running time of the algorithm would be: $O(n)$ $O(\log n)$ $O(n\log n)$ $O(n^2)$

Consider the algorithm that solves problems of size $n$ by recursively solving two sub problems of size $n-1$ and then combining the solutions in constant time. Then the ...

gatecse

1.2k views

gatecse asked Dec 9, 2020

1 votes

1 answer

276

NIELIT Scientific Assistant A 2020 November: 64
Which of the following is a correct time complexity to solve the $0/1$ knapsack problem where $n$ and $w$ represents the number of items and capacity of knapsack respectively? $O(n)$ $O(w)$ $O(nw)$ $O(n+w)$

Which of the following is a correct time complexity to solve the $0/1$ knapsack problem where $n$ and $w$ represents the number of items and capacity of knapsack respecti...

gatecse

668 views

gatecse asked Dec 9, 2020

3 votes

1 answer

277

NIELIT Scientific Assistant A 2020 November: 101
What is the time complexity of the following recursive function? int ComputFun(int n) { if(n<=2) return 1; else return (ComputFun(floor(sqrt(n)))+n); } $\Theta(n)$ $\Theta(\log n)$ $\Theta(n\log n)$ $\Theta(\log \log n)$

What is the time complexity of the following recursive function?int ComputFun(int n) { if(n<=2) return 1; else return (ComputFun(floor(sqrt(n)))+n); }$\Theta(n)$$\Theta(\...

gatecse

902 views

gatecse asked Dec 9, 2020

0 votes

1 answer

278

UGC NET CSE | October 2020 | Part 2 | Question: 25
If algorithm $A$ and another algorithm $B$ take $\log_2 (n)$ and $\sqrt{n}$ microseconds, respectively, to solve a problem, then the largest size $n$ of a problem these algorithms can solve, respectively, in one second are ______ and ______. $2^{10^n}$ and $10^6$ $2^{10^n}$ and $10^{12}$ $2^{10^n}$ and $6.10^6$ $2^{10^n}$ and $6.10^{12}$

If algorithm $A$ and another algorithm $B$ take $\log_2 (n)$ and $\sqrt{n}$ microseconds, respectively, to solve a problem, then the largest size $n$ of a problem these a...

go_editor

2.3k views

go_editor asked Nov 20, 2020

2 votes

4 answers

279

UGC NET CSE | October 2020 | Part 2 | Question: 52
The running time of an algorithm is $O(g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n)) \cdot (O= \textit{ big }O)$ its worst-case running time is $\Omega (g(n))$ and its best-case running ... $O(g(n))\cap \omega(g(n))$ is non-empty set, $(o = \textit{ small } o)$

The running time of an algorithm is $O(g(n))$ if and only ifits worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n)) \cdot (O= \textit{ bi...

go_editor

1.9k views

go_editor asked Nov 20, 2020

2 votes

1 answer

280

GATE Overflow Test Series | Algorithms | Test 2 | Question: 11
If the worst case time complexity by the best algorithm for finding the outdegrees and indegrees of all the vertices (extra space can be used if required) in a dense graph of $n$ vertices (number of edges $= \Theta(n^2))$ represented in Adjacency List ... $2\times a + 3 \times b + 5 \times c + 7 \times d = $ _____

If the worst case time complexity by the best algorithm for finding the outdegrees and indegrees of all the vertices (extra space can be used if required) in a dense grap...

gatecse

445 views

gatecse asked Sep 7, 2020

1 votes

1 answer

281

GATE Overflow Test Series | Mixed Subjects | Test 2 | Question: 5
For the below function, arr is pointing to an array of $len$ elements. The complexity of the function is void func(int * arr, int len) { if(len == 0) return; printf("%d ", arr[0]); func(arr+1, len-1); } $O(n)$ $\Theta( n^2)$ $O(1)$ $\Theta(n \log n)$

For the below function, arr is pointing to an array of $len$ elements. The complexity of the function isvoid func(int * arr, int len) { if(len == 0) return; printf("%d ",...

gatecse

75 views

gatecse asked Aug 30, 2020

9 votes

2 answers

282

GATE Overflow Test Series | Algorithms | Test 1 | Question: 11
Given an array of $n$ elements, you have to design an algorithm to find the $k$ smallest elements in sorted order. The time complexity of the best such algorithm assuming comparison based sorting will be $O(k \log n)$ $\Theta(n + k \log k)$ $\Theta(n^2)$ $\Theta (n \log k)$

Given an array of $n$ elements, you have to design an algorithm to find the $k$ smallest elements in sorted order. The time complexity of the best such algorithm assuming...

gatecse

629 views

gatecse asked Aug 18, 2020

3 votes

1 answer

283

GATE Overflow Test Series | Algorithms | Test 1 | Question: 18
What is the time complexity of following code if $foo(n)$ takes $\Theta(\log n)$ time to execute? int i, j; for (i = n / 2; i <= n; i++) { for (j = 1; j <= n; j = j * 2) { foo(j); } } $\Theta(n)$ $\Theta(n \lg n)^2$ $\Theta(n (\lg n)^2)$ $\Theta(n^2 \lg n)$

What is the time complexity of following code if $foo(n)$ takes $\Theta(\log n)$ time to execute?int i, j; for (i = n / 2; i <= n; i++) { for (j = 1; j <= n; j = j * 2) {...

gatecse

201 views

gatecse asked Aug 18, 2020

3 votes

1 answer

284

GATE Overflow Test Series | Algorithms | Test 1 | Question: 19
The return value, time complexity and space complexity of following code are int foo(int n) { int a = 0; while (n > 0) { a += n; n /= 2; } return a; } $\Theta(\log n),\Theta(\log n),\Theta(\log n)$ $\Theta(n),\Theta(\log n),O(1)$ $\Theta(\log n),\Theta(\log n),O(1)$ $\Theta(n^2),O( n),O(1)$

The return value, time complexity and space complexity of following code areint foo(int n) { int a = 0; while (n 0) { a += n; n /= 2; } return a; }$\Theta(\log n),\Theta...

gatecse

242 views

gatecse asked Aug 18, 2020

5 votes

1 answer

285

GATE Overflow Test Series | Algorithms | Test 1 | Question: 26
Maximum Subarray Sum problem is to find the subarray with maximum sum. For example, given an array $\{12, -13, -5, 25, -20, 30, 10\}$, the maximum subarray sum is $45$. The best possible algorithm to compute the maximum subarray sum will run in (Mark all the appropriate choices) $O(n)$ `$\Omega(n \log n)$ $O( \log n)$ $O(n^2)$

Maximum Subarray Sum problem is to find the subarray with maximum sum. For example, given an array $\{12, -13, -5, 25, -20, 30, 10\}$, the maximum subarray sum is $45$. T...

gatecse

467 views

gatecse asked Aug 18, 2020

6 votes

3 answers

286

GATE Overflow Test Series | Algorithms | Test 1 | Question: 27
You are given an array $A$ of $n$ elements. The best possible algorithm to find two numbers in $A$ which sum to the largest number in $A$ will run in (assuming comparison based sorting) (Mark all CORRECT choices) $O(n)$ `$\Omega(n \log n)$ $\Omega( n^2\log n)$ $O(n^2)$

You are given an array $A$ of $n$ elements. The best possible algorithm to find two numbers in $A$ which sum to the largest number in $A$ will run in (assuming comparison...

gatecse

474 views

gatecse asked Aug 18, 2020

1 votes

1 answer

287

GATE Overflow Test Series | Data Structures | Test 1 | Question: 12
The time complexity of the below code is int isPalindrome ( char * string, int n ) { if (n <= 1) return 1; if (string[0] != string[n-1]) return 0; return isPalindrome(string + 1, n-2); } $\Theta(n)$ $\Theta (n \log n)$ $\Theta(\log n)$ $\Theta(n^2)$

The time complexity of the below code isint isPalindrome ( char * string, int n ) { if (n <= 1) return 1; if (string[0] != string[n-1]) return 0; return isPalindrome(stri...

gatecse

294 views

gatecse asked Aug 9, 2020

3 votes

1 answer

288

GATE Overflow Test Series | Data Structures | Test 1 | Question: 18
Let $f(n),g(n)$ and $h(n)$ be the time complexities of three programs. Let $f(n) = O(g(n))$ and $h(n) = O(g(n)).$ Which of the following is necessarily FALSE? $f(n) = O(h(n))$ $g(n) = O(f(n))$ $h(n) = \Omega(g(n))$ None of the above are necessarily FALSE

Let $f(n),g(n)$ and $h(n)$ be the time complexities of three programs. Let $f(n) = O(g(n))$ and $h(n) = O(g(n)).$ Which of the following is necessarily FALSE?$f(n) = O(h(...

gatecse

319 views

gatecse asked Aug 9, 2020

1 votes

2 answers

289

GATE Overflow Test Series | Data Structures | Test 1 | Question: 25
Let $f(n),g(n)$ and $h(n)$ be the time complexities of three programs and let $f(n) = o(g(n))$ and $h(n) = \omega(g(n)).$ Which of the following is VALID? $f(n) = \Theta(h(n))$ $g(n) = O(f(n))$ $h(n) = \Omega(g(n))$ $g(n) = \Omega(h(n))$

Let $f(n),g(n)$ and $h(n)$ be the time complexities of three programs and let $f(n) = o(g(n))$ and $h(n) = \omega(g(n)).$ Which of the following is VALID?$f(n) = \Theta(h...

gatecse

262 views

gatecse asked Aug 9, 2020

3 votes

2 answers

290

NIELIT 2016 MAR Scientist C - Section C: 51
The most efficient algorithm for finding the number of connected components in a $n$ undirected graph on $n$ vertices and $m$ edges has time complexity $\Theta (n)$ $\Theta (m)$ $\Theta (m+n)$ $\Theta (mn)$

The most efficient algorithm for finding the number of connected components in a $n$ undirected graph on $n$ vertices and $m$ edges has time complexity$\Theta (n)$$\Theta...

admin

920 views

admin asked Apr 2, 2020

3 votes

1 answer

291

NIELIT 2016 MAR Scientist C - Section C: 52
Consider the process of inserting an element into a $Max\ Heap$, where the $Max\ Heap$ is represented by an $array$. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of $comparisons$ ... $\Theta(n\log _{2} \log_2 n)$ $\Theta (n)$ $\Theta(n\log _{2}n)$

Consider the process of inserting an element into a $Max\ Heap$, where the $Max\ Heap$ is represented by an $array$. Suppose we perform a binary search on the path from ...

admin

1.9k views

admin asked Apr 2, 2020

0 votes

1 answer

292

NIELIT 2017 OCT Scientific Assistant A (IT) - Section C: 2
An algorithm is made up pf two modules $M1$ and $M2.$ If order of $M1$ is $f(n)$ and $M2$ is $g(n)$ then the order of algorithm is $max(f(n),g(n))$ $min(f(n),g(n))$ $f(n) + g(n)$ $f(n) \times g(n)$

An algorithm is made up pf two modules $M1$ and $M2.$ If order of $M1$ is $f(n)$ and $M2$ is $g(n)$ then the order of algorithm is$max(f(n),g(n))$$min(f(n),g(n))$$f(n) + ...

admin

938 views

admin asked Apr 1, 2020

0 votes

0 answers

293

NIELIT 2017 OCT Scientific Assistant A (IT) - Section B: 14
The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by $T(n) = 8T(n/2) + qn,$ if $n>1$ $= p,$ if $n = 1$ Where $p,q$ are constants. The order of this algorithm is $n^{2}$ $n^{n}$ $n^{3}$ $n$

The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by$T(n) = 8T(n/2) + qn,$ if $n>1$ $= p,$ if $n = 1$Where $p,q$ are constan...

admin

878 views

admin asked Apr 1, 2020

1 votes

1 answer

294

NIELIT 2017 OCT Scientific Assistant A (CS) - Section C: 4
The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by $T(n) = 8T(n/2) + qn,$ if $n>1$ $ = p,$ if $n = 1$ Where $p,q$ are constants. The order of this algorithm is $n^{2}$ $n^{n}$ $n^{3}$ $n$

The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by$T(n) = 8T(n/2) + qn,$ if $n>1$$ = p,$ if $n = 1$Where $p,q$ are constants. The or...

admin

1.3k views

admin asked Apr 1, 2020

2 votes

3 answers

295

NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 8
Consider the following C code segment: int Ls Prime(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 the number of times the for loop is executed by the program on input $n.$ ... $T(n) = \Omega (1)$ $T(n) = O(n)$ and $T(n) = \Omega (\sqrt{n})$ None of these

Consider the following C code segment:int Ls Prime(n) { int i,n; for(i=2;i<=sqrt(n);i++) if(n%i ==0) { printf(“NOT Prime.\n”); ...

admin

868 views

admin asked Apr 1, 2020

1 votes

3 answers

296

NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 30
An algorithm is made up of two modules $M1$ and $M2.$ If order of $M1$ is $f(n)$ and $M2$ is $g(n)$ then he order of algorithm is $max(f(n),g(n))$ $min(f(n),g(n))$ $f(n) + g(n)$ $f(n) \times g(n)$

An algorithm is made up of two modules $M1$ and $M2.$ If order of $M1$ is $f(n)$ and $M2$ is $g(n)$ then he order of algorithm is$max(f(n),g(n))$$min(f(n),g(n))$$f(n) + g...

admin

1.0k views

admin asked Apr 1, 2020

4 votes

11 answers

297

NIELIT 2016 MAR Scientist B - Section C: 12
Which of the following sorting algorithms does not have a worst case running time of $O(n^2)$? Insertion sort. Merge sort. Quick sort. Bubble sort.

Which of the following sorting algorithms does not have a worst case running time of $O(n^2)$?Insertion sort.Merge sort.Quick sort.Bubble sort.

admin

15.6k views

admin asked Mar 31, 2020

1 votes

2 answers

298

NIELIT 2016 MAR Scientist B - Section C: 22
Time complexity of an algorithm $T(n)$, where $n$ is the input size is given by $\begin{array}{ll}T(n) & =T(n-1)+\frac{1}{n}, \text{ if }n>1\\ & =1, \text{ otherwise} \end{array}$ The order of this algorithm is $\log n$ $n$ $n^2$ $n^n$

Time complexity of an algorithm $T(n)$, where $n$ is the input size is given by$\begin{array}{ll}T(n) & =T(n-1)+\frac{1}{n}, \text{ if }n>1\\ & =1, \text{ otherwise} \en...

admin

1.4k views

admin asked Mar 31, 2020

5 votes

2 answers

299

NIELIT 2016 DEC Scientist B (IT) - Section B: 27
Complexity of Kruskal's algorithm for finding minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is: $O(mn)$ $O(m)$ $O(m+n)$ $O(n)$

Complexity of Kruskal's algorithm for finding minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is:$O(mn)$$O(m)$$...

admin

1.8k views

admin asked Mar 31, 2020

4 votes

4 answers

300

NIELIT 2016 DEC Scientist B (CS) - Section B: 16
Two main measures for the efficiency of an algorithm are: Processor and Memory Complexity and Capacity Time and Space Data and Space

Two main measures for the efficiency of an algorithm are:Processor and MemoryComplexity and CapacityTime and SpaceData and Space

admin

84.5k views

admin asked Mar 31, 2020

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true