menu
search
Log In
Quick search syntax
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

Subjects

Recent questions tagged time-complexity

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions tagged time-complexity

0 votes
1 answer
1
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 the new leaf to the root to find the position for the newly inserted element, the number of $comparisons$ performed is $\Theta(\log _{2}n)$ $\Theta(n\log _{2} \log_2 n)$ $\Theta (n)$ $\Theta(n\log _{2}n)$
asked Apr 2 in DS Lakshman Patel RJIT 41 views
0 votes
2 answers
2
NIELIT 2017 July Scientist B (IT) - Section B: 59
What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$
What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$
asked Mar 30 in Algorithms Lakshman Patel RJIT 183 views
3 votes
4 answers
3
TIFR2020-B-10
Among the following asymptotic expressions, which of these functions grows the slowest (as a function of $n$) asymptotically? $2^{\log n}$ $n^{10}$ $(\sqrt{\log n})^{\log ^{2} n}$ $(\log n)^{\sqrt{\log n}}$ $2^{2^{\sqrt{\log\log n}}}$
Among the following asymptotic expressions, which of these functions grows the slowest (as a function of $n$) asymptotically? $2^{\log n}$ $n^{10}$ $(\sqrt{\log n})^{\log ^{2} n}$ $(\log n)^{\sqrt{\log n}}$ $2^{2^{\sqrt{\log\log n}}}$
asked Feb 11 in Algorithms Lakshman Patel RJIT 388 views
5 votes
2 answers
4
ISRO2020-36
What is the complexity of the following code? sum=0; for(i=1;i<=n;i*=2) for(j=1;j<=n;j++) sum++; Which of the following is not a valid string? $O(n^2)$ $O(n\log\ n)$ $O(n)$ $O(n\log\ n\log\ n)$
What is the complexity of the following code? sum=0; for(i=1;i<=n;i*=2) for(j=1;j<=n;j++) sum++; Which of the following is not a valid string? $O(n^2)$ $O(n\log\ n)$ $O(n)$ $O(n\log\ n\log\ n)$
asked Jan 13 in Algorithms Satbir 730 views
1 vote
1 answer
5
IIIT BLR TEST 1 : ALGORITHMS 3
Given an array of ( both positive and negative ) integers, $a_0,a_1,….a_{n-1}$ and $l, 1<l<n$. Design a linear time algorithm to compute the maximum product subarray, whose length is atmost $l$.
Given an array of ( both positive and negative ) integers, $a_0,a_1,….a_{n-1}$ and $l, 1<l<n$. Design a linear time algorithm to compute the maximum product subarray, whose length is atmost $l$.
asked Aug 27, 2019 in Algorithms Shaik Masthan 418 views
0 votes
1 answer
6
IIIT BLR TEST 1 : ALGORITHMS 1
​​​​​​Solve the following recursions ( in terms of Θ ). T(0) = T(1) = Θ(1) in all of the following. $T(n) = n + \frac{1}{n}\sum_{i=0}^{i=n-1}T(i)$ $T(n) = n + \frac{2}{n}\sum_{i=0}^{i=n-1}T(i)$ $T(n) = n + \frac{4}{n}\sum_{i=0}^{i=n/2}T(i)$ $T(n) = n + \frac{40}{n}\sum_{i=0}^{i=n/5}T(i)$
​​​​​​Solve the following recursions ( in terms of Θ ). T(0) = T(1) = Θ(1) in all of the following. $T(n) = n + \frac{1}{n}\sum_{i=0}^{i=n-1}T(i)$ $T(n) = n + \frac{2}{n}\sum_{i=0}^{i=n-1}T(i)$ $T(n) = n + \frac{4}{n}\sum_{i=0}^{i=n/2}T(i)$ $T(n) = n + \frac{40}{n}\sum_{i=0}^{i=n/5}T(i)$
asked Aug 27, 2019 in Algorithms Shaik Masthan 253 views
0 votes
1 answer
7
Cormen Edition 3 Exercise 7.4 Question 4 (Page No. 184)
Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.
Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.
asked Jun 28, 2019 in Algorithms akash.dinkar12 129 views
0 votes
2 answers
9
Cormen Edition 3 Exercise 7.2 Question 3 (Page No. 178)
Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.
Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.
asked Jun 27, 2019 in Algorithms akash.dinkar12 68 views
1 vote
1 answer
10
Cormen Edition 3 Exercise 7.2 Question 2 (Page No. 178)
What is the running time of QUICKSORT when all elements of the array $A$ have the same value?
What is the running time of QUICKSORT when all elements of the array $A$ have the same value?
asked Jun 27, 2019 in Algorithms akash.dinkar12 109 views
0 votes
1 answer
11
Cormen Edition 3 Exercise 2.3 Question 3 (Page No. 39)
Use mathematical induction to show that when $n$ is an exact power of $2$, the solution of the recurrence $T(n) = \begin{cases} 2 \text{, if n=2, } \\2T(n/2)+n \text{, if n=$2^k$,for k >1} \end{cases}$ is $T(n) = n\ lg\ n$.
Use mathematical induction to show that when $n$ is an exact power of $2$, the solution of the recurrence $T(n) = \begin{cases} 2 \text{, if n=2, } \\2T(n/2)+n \text{, if n=$2^k$,for k >1} \end{cases}$ is $T(n) = n\ lg\ n$.
asked Jun 26, 2019 in Algorithms akash.dinkar12 98 views
0 votes
1 answer
12
Cormen Edition 3 Exercise 2.3 Question 4 (Page No. 38)
We can express the insertion sort as a recursive procedure as follows.In order to sort $A[1\dots n]$, we recursively sort $A[1 \dots n-1]$ and then insert $A[n]$ into the sorted array $A[1 \dots n-1]$. Write a recurrence for the running time of this recursive version of insertion sort.
We can express the insertion sort as a recursive procedure as follows.In order to sort $A[1\dots n]$, we recursively sort $A[1 \dots n-1]$ and then insert $A[n]$ into the sorted array $A[1 \dots n-1]$. Write a recurrence for the running time of this recursive version of insertion sort.
asked Jun 26, 2019 in Algorithms akash.dinkar12 84 views
0 votes
1 answer
13
Cormen Edition 3 Exercise 2.2 Question 2 (Page No. 29)
Consider sorting $n$ numbers stored in an array $A$ by first finding the smallest element of $A$ and exchanging it with the element in $A[1]$. Then find the second smallest element of $A$ ... , rather than for all n elements? Give the best-case and worst-case running times of selection sort in $\Theta$-notation
Consider sorting $n$ numbers stored in an array $A$ by first finding the smallest element of $A$ and exchanging it with the element in $A[1]$. Then find the second smallest element of $A$, and exchange it with $A[2] $. Continue in this manner for the first ... $n-1$ elements, rather than for all n elements? Give the best-case and worst-case running times of selection sort in $\Theta$-notation
asked Jun 25, 2019 in Algorithms akash.dinkar12 162 views
0 votes
2 answers
14
Cormen Edition 3 Exercise 2.2 Question 1 (Page No. 29)
Express the function $n^3/1000 -100n^2-100n+3$ in terms of $\Theta$ notation.
Express the function $n^3/1000 -100n^2-100n+3$ in terms of $\Theta$ notation.
asked Jun 25, 2019 in Algorithms akash.dinkar12 126 views
0 votes
0 answers
15
Is each and every NP complete problem (polynomially) reduced to each and every another NP complete problem?
I know that all NP problems can be reduced to Boolean Satisfiability SAT problem. But my question is whether SAT problem can be reduced to other NP complete problems like travelling salesperson problem TSP, 0/1 knapsack problem. In short are the reductions in NPC problems two ways?
asked Jun 13, 2019 in Theory of Computation commenter commenter 85 views
0 votes
1 answer
16
Master's Theorem: Validity of Format
How to check if a given recurrence relation is in a format that is valid to apply Master’s Theorem? Also, how to distinguish between Master’s Theorem and extended Master’s Theorem?
How to check if a given recurrence relation is in a format that is valid to apply Master’s Theorem? Also, how to distinguish between Master’s Theorem and extended Master’s Theorem?
asked Jun 12, 2019 in Algorithms lolster 198 views
2 votes
1 answer
17
GATE-1999
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 ... $c$ So complexity should be $O(1)$. But answer is $O(n)$.What I am doing wrong?
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 ... $c$ So complexity should be $O(1)$. But answer is $O(n)$.What I am doing wrong?
asked Jun 4, 2019 in Algorithms kshitij 207 views
1 vote
2 answers
18
Asymptotic Notation theta property
If $T1(n) = \Theta(f(n))$ & $T2(n) = \Theta(f(n))$ Then, Is $T1(n) + T2(n) = O(f(n))$ If yes, then how?
If $T1(n) = \Theta(f(n))$ & $T2(n) = \Theta(f(n))$ Then, Is $T1(n) + T2(n) = O(f(n))$ If yes, then how?
asked May 26, 2019 in Algorithms shubhojit1412 350 views
1 vote
3 answers
19
Made easy Workbook 2020
Question: $T(1)=1$ $T(n) = 2 T(n - 1) + n$ evaluates to? Can anyone solve it by substitution method? Given answer $T(n) = 2^{n+1} - (n+2)$ How?
Question: $T(1)=1$ $T(n) = 2 T(n - 1) + n$ evaluates to? Can anyone solve it by substitution method? Given answer $T(n) = 2^{n+1} - (n+2)$ How?
asked May 25, 2019 in Algorithms Jyoti Kumari97 2.7k views
0 votes
0 answers
21
Made Easy Test Series: Algorithm-Reverse Polish Notation
Consider the new-order strategy for traversing a binary tree: Visit the root Visit the right subtree using new-order Visit the left subtree using new-order The new-order traversal of expression tree corresponding to the reverse polish expression 3 4 * 5 – 2 ^ 6 7 * 1 + – What will be expression, any procedure for it??
Consider the new-order strategy for traversing a binary tree: Visit the root Visit the right subtree using new-order Visit the left subtree using new-order The new-order traversal of expression tree corresponding to the reverse polish expression 3 4 * 5 – 2 ^ 6 7 * 1 + – What will be expression, any procedure for it??
asked May 16, 2019 in Compiler Design srestha 150 views
0 votes
3 answers
22
Made Easy Test Series:Algorithm-Recurrence Relation
What is the solution of recurrence relation $T\left ( n \right )=T\left ( n-1 \right )+n$
What is the solution of recurrence relation $T\left ( n \right )=T\left ( n-1 \right )+n$
asked May 10, 2019 in Algorithms srestha 245 views
1 vote
0 answers
23
GO screening test
Which one of the following notations is most relevant for finding the best algorithm for a problem? (A) $o(f(n))$ (B) $O(f(n))$ (C) $\omega (f(n))$ (D) $ \Omega (f(n))$
Which one of the following notations is most relevant for finding the best algorithm for a problem? (A) $o(f(n))$ (B) $O(f(n))$ (C) $\omega (f(n))$ (D) $ \Omega (f(n))$
asked May 9, 2019 in Algorithms toxicdesire 268 views
3 votes
1 answer
24
Made Easy Test Series:Time Complexity
Consider the following program: int Bar(int n){ if(n<2) return; } else{ int sum=0; int i,j; for(i=1;i<=4;i++) Bar(n/2); for(i=1;i<=n;i++){ for(j=1;j<=i;j++){ sum=sum+1; } } } Now consider the following ... $Bar\left ( n \right )$ is $O \left ( n^{3}logn^{2} \right )$ How many statements are correct________________
Consider the following program: int Bar(int n){ if(n<2) return; } else{ int sum=0; int i,j; for(i=1;i<=4;i++) Bar(n/2); for(i=1;i<=n;i++){ for(j=1;j<=i;j++){ sum=sum+1; } } } Now consider the following statement $S_{1}:$ The time complexity of ... $S_{3}:$The time complexity of $Bar\left ( n \right )$ is $O \left ( n^{3}logn^{2} \right )$ How many statements are correct________________
asked May 7, 2019 in Algorithms srestha 608 views
1 vote
2 answers
25
IIIT PGEE 2019
What is the time complexity to delete an arbitrary node from binary heap? O(n) O(log n) O(1) O(n log n)
What is the time complexity to delete an arbitrary node from binary heap? O(n) O(log n) O(1) O(n log n)
asked Apr 29, 2019 in Programming manikgupta123 472 views
0 votes
3 answers
26
IIIT PGEE 2019
Which of the following gives O(1) complexity if we want to check whether an edge exists between two given nodes in a graph? Adjacency List Adjacency Matrix Incidence Matrix None of these
Which of the following gives O(1) complexity if we want to check whether an edge exists between two given nodes in a graph? Adjacency List Adjacency Matrix Incidence Matrix None of these
asked Apr 29, 2019 in DS manikgupta123 394 views
2 votes
2 answers
27
IIIT PGEE 2019
What is the time complexity for insertion in binary tree in worst case? O(1) O(log n) O(n) O(n log n)
What is the time complexity for insertion in binary tree in worst case? O(1) O(log n) O(n) O(n log n)
asked Apr 29, 2019 in Programming manikgupta123 405 views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...