Recent questions tagged time-complexity

+2 votes

1 answer

1

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)$

asked Jan 13 in Algorithms by Satbir Boss (24.2k points) | 248 views

+1 vote

1 answer

2

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$.

asked Aug 27, 2019 in Algorithms by Shaik Masthan Veteran (65.8k points) | 245 views

0 votes

1 answer

3

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)$

asked Aug 27, 2019 in Algorithms by Shaik Masthan Veteran (65.8k points) | 144 views

0 votes

1 answer

4

Cormen Edition 3 Exercise 7.4 Question 4 (Page No. 184)
Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.

asked Jun 28, 2019 in Algorithms by akash.dinkar12 Boss (42.5k points) | 74 views

0 votes

2 answers

5

Cormen Edition 3 Exercise 7.4 Question 2 (Page No. 184)
Show that quicksort’s best-case running time is $\Omega(n\ lg\ n)$.

asked Jun 28, 2019 in Algorithms by akash.dinkar12 Boss (42.5k points) | 38 views

0 votes

1 answer

6

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.

asked Jun 27, 2019 in Algorithms by akash.dinkar12 Boss (42.5k points) | 26 views

+1 vote

1 answer

7

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?

asked Jun 27, 2019 in Algorithms by akash.dinkar12 Boss (42.5k points) | 58 views

0 votes

1 answer

8

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$.

asked Jun 26, 2019 in Algorithms by akash.dinkar12 Boss (42.5k points) | 55 views

0 votes

1 answer

9

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.

asked Jun 26, 2019 in Algorithms by akash.dinkar12 Boss (42.5k points) | 42 views

0 votes

1 answer

10

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

asked Jun 25, 2019 in Algorithms by akash.dinkar12 Boss (42.5k points) | 35 views

0 votes

2 answers

11

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.

asked Jun 25, 2019 in Algorithms by akash.dinkar12 Boss (42.5k points) | 70 views

0 votes

0 answers

12

Is each and every NP complete problem (polynomially) reduced to each and every another NP complete problem?

asked Jun 13, 2019 in Theory of Computation by commenter commenter Active (1.6k points) | 49 views

0 votes

1 answer

13

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?

asked Jun 12, 2019 in Algorithms by lolster (237 points) | 114 views

+1 vote

0 answers

14

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?

asked Jun 4, 2019 in Algorithms by kshitij (295 points) | 139 views

0 votes

1 answer

15

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?

asked May 26, 2019 in Algorithms by shubhojit1412 (5 points) | 168 views

+1 vote

3 answers

16

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?

asked May 25, 2019 in Algorithms by Jyoti Kumari97 (187 points) | 810 views

+3 votes

0 answers

17

Made Easy Test Series:Algorithm-Time Complexity
Consider a procedure $find()$ which take array of $n$ integers as input, and produce pair of element of array whose difference is not greater than the difference of any other pair of element of that array. Which of the following represent ... Here we need to sort first and then need to compare adjacent element right?? Then what will be complexity??

asked May 18, 2019 in Algorithms by srestha Veteran (119k points) | 254 views

0 votes

0 answers

18

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??

asked May 16, 2019 in Compiler Design by srestha Veteran (119k points) | 109 views

0 votes

1 answer

19

Made Easy Test Series:Algorithm-Recurrence Relation
What is the solution of recurrence relation $T\left ( n \right )=T\left ( n-1 \right )+n$

asked May 10, 2019 in Algorithms by srestha Veteran (119k points) | 159 views

+1 vote

0 answers

20

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))$

asked May 9, 2019 in Algorithms by toxicdesire Active (2k points) | 179 views

+3 votes

1 answer

21

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________________

asked May 7, 2019 in Algorithms by srestha Veteran (119k points) | 382 views

+1 vote

1 answer

22

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)

asked Apr 29, 2019 in Programming by manikgupta123 (81 points) | 173 views

0 votes

1 answer

23

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

asked Apr 29, 2019 in DS by manikgupta123 (81 points) | 153 views

+2 votes

1 answer

24

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)

asked Apr 29, 2019 in Programming by manikgupta123 (81 points) | 195 views

+1 vote

1 answer

25

If there is an $\rm NP$-complete language $L$ whose complement is in $\rm NP$, then...

asked Apr 20, 2019 in Theory of Computation by Rhythm (195 points) | 124 views

+1 vote

0 answers

26

Find Asymptotic upper bound (http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf)

asked Apr 19, 2019 in Algorithms by Mk Utkarsh Boss (36.6k points) | 124 views

0 votes

0 answers

27

Algorithm Time Complexity-Self Doubt
What is the best case and worst case of the algorithm? And when will best case and worst case will happen?? int main() { for(i=1 ; i<=n ; i++) { if(n%i == 0) { for(j=1 ; j<=n ; j++) { printf("Hello"); } } } }

asked Apr 10, 2019 in Algorithms by sumitr (235 points) | 196 views

0 votes

1 answer

28

Time complexity
Please help to find the time complexity of this loop. void main() { int n; while(n>=1) { n=n-2; } }

asked Mar 19, 2019 in Algorithms by Devshree Dubey Boss (13.8k points) | 120 views

0 votes

2 answers

29

Self doubt
O(n-1)+O(n)=O(n) O(n/2)+O(n)=O(n) but O(1)+O(2)+O(3)+...+O(n)=O(n(n+1)/2)=O(n^2) why?

asked Mar 19, 2019 in Algorithms by Tanuj Guha Thakurta (175 points) | 84 views

0 votes

0 answers

30

Time complexity
Is this the correct way to solve ? Q) int algorithm(int n) { int sum =0;k,j; for (k=0;k<n/2;k++) for(j=0;j<10;j++) sum++; return 4*algorithm(n/2)*algorithm(n/2)+algorithm(n/2)*algorithm(n/2) }

asked Mar 15, 2019 in Algorithms by syncronizing Junior (835 points) | 163 views

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

Recent questions tagged time-complexity

Recent Posts

Recent Blog Comments