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

0 votes

1 answer

1

Prove that n! = Ω(n^100)

wtquevb123

88 views

wtquevb123 asked Mar 14

0 votes

1 answer

2

Sorting Algorithm
For flag based approach in Bubble sort we can check first by a flag if the list is sorted or not in O(n), and if it is sorted, then no need to sort and the operation ends in Best case = O(n). Why isn't the same concept applicable to selection sort? Why it never comes down from O(n$^2$)?

For flag based approach in Bubble sort we can check first by a flag if the list is sorted or not in O(n), and if it is sorted, then no need to sort and the operation ends...

Mrityudoot

191 views

Mrityudoot asked Mar 7

2 votes

1 answer

3

GATE CSE 2024 | Set 1 | Question: 7
Given an integer array of size $N$, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The ... $\Omega(N)$ but not $\mathrm{O}(N)$ neither $\mathrm{O}(N)$ nor $\Omega(N)$

Given an integer array of size $N$, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single...

Arjun

3.3k views

Arjun asked Feb 16

5 votes

1 answer

4

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 17
Consider the following function. If $n$ and $\mathrm{k}$ are positive integers, then the least value of $\mathrm{k}$ such that $\mathrm{f}(\mathrm{k})>n$ is approximately $\log _2\left(\log _2 n\right)$ $\log _2 n$ $n \log _2 n$ $2^n$

Consider the following function.If $n$ and $\mathrm{k}$ are positive integers, then the least value of $\mathrm{k}$ such that $\mathrm{f}(\mathrm{k})>n$ is approximately$...

GO Classes

497 views

GO Classes asked Feb 5

4 votes

1 answer

5

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 46
We have a procedure $P(n)$ that makes multiple calls to a procedure $Q(m)$, and runs in polynomial time in $n$. Unfortunately, a significant flaw was discovered in $Q(m)$, and it had to be replaced by $R(m)$, which runs in exponential ... $P(n)$ runs in polynomial time in $n$ if, for each call $Q(m),m \underline<\log \;n.$

We have a procedure $P(n)$ that makes multiple calls to a procedure $Q(m)$, and runs in polynomial time in $n$. Unfortunately, a significant flaw was discovered in $Q(m)$...

GO Classes

437 views

GO Classes asked Feb 5

7 votes

3 answers

6

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 40
You are given a complete binary tree (each level must be full except the last) on $n$ vertices. Each vertex $v$ is labeled by an integer value $x_v$. Say that a vertex is a local minimum if its label is less than the labels of each of its ... minimum in the tree? $\theta(n)$ $\theta(\sqrt{n})$ $\theta(\log n)$ $\theta(n \log n)$

You are given a complete binary tree (each level must be full except the last) on $n$ vertices. Each vertex $v$ is labeled by an integer value $x_v$. Say that a vertex is...

GO Classes

792 views

GO Classes asked Jan 28

5 votes

1 answer

7

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 30
Consider the following pseudocode for a function that operates on an $\textsf{N}$ element array $\textsf{A[1],A[2]},\dots,\textsf{A[N]}$ of integers. function mystery (A[1...N]) { int i,j,position,tmp; for i=1 to N { position= ... ; } } If $\textsf{N = 100,}$ how many times is the comparison $\textsf{A[j] < A[position]}$ checked?

Consider the following pseudocode for a function that operates on an $\textsf{N}$ element array $\textsf{A ,A },\dots,\textsf{A[N]}$ of integers.function mystery (A[1...N...

GO Classes

517 views

GO Classes asked Jan 21

3 votes

3 answers

8

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 54
Of the following, which gives the best upper bound for the value of $f(N)$ where $f$ is a solution to the recurrence $ f(2 N+1)=f(2 N)=f(N)+\log N \text { for } N \geq 1, $ with $f(1)=0?$ $O(\log N)$ $O(N \log N)$ $O\left((\log N)^2\right)$ $O(N)$

Of the following, which gives the best upper bound for the value of $f(N)$ where $f$ is a solution to the recurrence$$f(2 N+1)=f(2 N)=f(N)+\log N \text { for } N \geq 1,$...

GO Classes

893 views

GO Classes asked Jan 21

12 votes

2 answers

9

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 50
Given an unsorted array of $n$ distinct elements, you want to find this set of $\log n$ elements: those at positions $1,2,4,8,16, \ldots, n/2$ if array were sorted. In other words, find the largest element, the second largest element, the ... the subarray) $\Theta(\log n)$ $\Theta(n)$ $\Theta(n \log n)$ $\Theta\left(n^{2}\right)$

Given an unsorted array of $n$ distinct elements, you want to find this set of $\log n$ elements: those at positions $1,2,4,8,16, \ldots, n/2$ if array were sorted. In ot...

GO Classes

981 views

GO Classes asked Jan 13

1 votes

1 answer

10

made-easy

Rohit Chakraborty

156 views

Rohit Chakraborty asked Jan 7

0 votes

1 answer

11

ISRO 2024
The complexity of matrix multiplication of two matrices A and B whose orders are $m \times n$ and $n \times p$ respectively is $\text{O(m} \times p)$ $\text{O(m} \times n^2 \times p)$ $\text{O(m} \times n \times p^2)$ $\text{O(m} \times n \times p)$

The complexity of matrix multiplication of two matrices A and B whose orders are $m \times n$ and $n \times p$ respectively is$\text{O(m} \times p)$$\text{O(m} \times n^2...

Ramayya

241 views

Ramayya asked Jan 7

1 votes

1 answer

12

UGC NET CSE | June 2008 | Part 2 | Question: 23
Which of the following is true for a sorted list with ' $n$ ... $\mathrm{O}(\log n)$ time.

Which of the following is true for a sorted list with ' $n$ ' elements?Insertion in a sorted array takes constant time.Insertion in a sorted linear linked list takes cons...

admin

142 views

admin asked Jan 6

0 votes

1 answer

13

#Applied Course
In a variant of quick sort, the n/10th smallest element is selected in every recursive call using a Θ(n) time algorithm, which is the worst-case time complexity for this sorting algorithm. T(n)=T(n/10)+T(9n/10)+O(n) This is what I tried according ... is getting calculated by o(n) in every recursive call can someone clarify this line what will be the effect of this on an algorithm?

In a variant of quick sort, the n/10th smallest element is selected in every recursive call using a Θ(n) time algorithm, which is the worst-case time complexity for this...

Dknights

197 views

Dknights asked Dec 16, 2023

0 votes

1 answer

14

TS
$\text{Please explain True or False and Why ?}$ $\text{1. f(n) = O(f(n/2))}$ $\text{2. f(n) = O($f(n)^{2}$) }$

$\text{Please explain True or False and Why ?}$$\text{1. f(n) = O(f(n/2))}$$\text{2. f(n) = O($f(n)^{2}$) }$

Jiten008

248 views

Jiten008 asked Dec 2, 2023

1 votes

1 answer

15

algorithm time complexity madeeasy
Consider the problem that given a set Sof n integers and another integer x, whether or not there exist two elements in S whose sum is exactly x. What is the worst case time complexity for the most efficient algorithm which solves the given problem? Is not it work like subset sum problem in dynamic programming? Then complexity should be O(n^2). How O(n logn)?

Consider the problem that given a set Sof n integers and another integer x, whether or not there exist two elements in S whose sum is exactly x. What is the worst case ti...

Sajal Mallick

495 views

Sajal Mallick asked Nov 28, 2023

0 votes

0 answers

16

algorithm time complexity madeeasy ots
What will be the complexity?

What will be the complexity?

Sajal Mallick

187 views

Sajal Mallick asked Nov 28, 2023

0 votes

0 answers

17

Algorithm Madeeasy Workbook
As we have to select maximal set of “non overlapping” activities. So like job scheduling algo of greedy we can solve it. So according to that complexity must be O(n logn). But ans is (b). Anyone please explain.

As we have to select maximal set of “non overlapping” activities. So like job scheduling algo of greedy we can solve it. So according to that complexity must be O(n l...

Sajal Mallick

185 views

Sajal Mallick asked Nov 27, 2023

0 votes

0 answers

18

Michael Sipser Decidability Problem
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. L = {M | M is a Turing machine and L(M) ∈ TIME(2^n)}

Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. ...

baofbuiafbi

146 views

baofbuiafbi asked Nov 14, 2023

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