# Recent questions tagged time-complexity

1
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)$
2
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)$
3
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}}}$
4
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)$
1 vote
5
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$.
6
​​​​​​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)$
7
Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.
8
Show that quicksort’s best-case running time is $\Omega(n\ lg\ n)$.
9
Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.
1 vote
10
What is the running time of QUICKSORT when all elements of the array $A$ have the same value?
11
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$.
12
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.
13
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
14
Express the function $n^3/1000 -100n^2-100n+3$ in terms of $\Theta$ notation.
15
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?
16
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?
17
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?
1 vote
18
If $T1(n) = \Theta(f(n))$ & $T2(n) = \Theta(f(n))$ Then, Is $T1(n) + T2(n) = O(f(n))$ If yes, then how?
1 vote
19
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?
20
Consider a procedure $find()$ which take array of $n$ ... Here we need to sort first and then need to compare adjacent element right?? Then what will be complexity??
21
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??
22
What is the solution of recurrence relation $T\left ( n \right )=T\left ( n-1 \right )+n$
1 vote
23
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))$
24
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________________
1 vote