Register

Recent questions tagged time-complexity

107
views
0 answers
0 votes
university assignment question
The array-based stack throws an exception when the array’s capacity has been reached. Consider the following alternative : create a larger array, using the resize metho...
User Avatar
172
views
1 answers
0 votes
Divide and conquer
In quick sort, n numbers the (n/10)th element is selected as pivot using n^2 sortimng time complexity what will be the time complexity of quick sort is.....a)O(nlogn)b)O(...
User Avatar
132
views
1 answers
2 votes
algorithms
for (i = 1; i <= N; i++){ for （j= 1;j <= i^2;j=j+i）{ //some code}} how is this O(n^2)? explain in detail and simple terms
User Avatar
133
views
1 answers
0 votes
Prove that n! = Ω(n^100)
User Avatar
279
views
1 answers
0 votes
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...
User Avatar
3.8k
views
1 answers
4 votes
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...
User Avatar
558
views
1 answers
5 votes
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$...
User Avatar
485
views
1 answers
5 votes
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)$...
User Avatar
910
views
3 answers
7 votes
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...
User Avatar
568
views
1 answers
5 votes
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 ,A },\dots,\textsf{A[N]}$ of integers.function mystery (A[1...N...
User Avatar
1.0k
views
3 answers
3 votes
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,$...
User Avatar
1.0k
views
2 answers
12 votes
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 ot...
User Avatar
177
views
1 answers
1 votes
made-easy
User Avatar
281
views
1 answers
0 votes
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...
User Avatar
190
views
1 answers
1 votes
UGC NET CSE | June 2008 | Part 2 | Question: 23
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...
User Avatar
227
views
1 answers
0 votes
#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...
User Avatar
289
views
1 answers
0 votes
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}$) }$
User Avatar
591
views
1 answers
1 votes
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 ti...
User Avatar
209
views
0 answers
0 votes
algorithm time complexity madeeasy ots
What will be the complexity?
User Avatar
215
views
0 answers
0 votes
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 l...
User Avatar
167
views
0 answers
0 votes
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. ...
User Avatar
Page: