search
Log In

Recent questions tagged time-complexity

1 vote
3 answers
1
​​​​​Let $H$ be a binary min-heap consisting of $n$ elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in $H$? $\Theta (1)$ $\Theta (\log n)$ $\Theta (n)$ $\Theta (n \log n)$
asked Feb 18 in DS Arjun 680 views
0 votes
2 answers
2
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$? $\Theta ( \sqrt{n})$ $\Theta (\log _2(n))$ $\Theta(n^2)$ $\Theta(n)$
asked Feb 18 in Algorithms Arjun 646 views
3 votes
3 answers
3
A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$? $\Theta(n\log n)$ $\Theta(n)$ $\Theta(\log n)$ $\Theta (1)$
asked Feb 18 in DS Arjun 653 views
4 votes
5 answers
4
Consider the following recurrence relation. $T\left ( n \right )=\left\{\begin{array} {lcl} T(n/2)+T(2n/5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.$ Which one of the following options is correct? $T(n)=\Theta (n^{5/2})$ $T(n)=\Theta (n\log n)$ $T(n)=\Theta (n)$ $T(n)=\Theta ((\log n)^{5/2})$
asked Feb 18 in Algorithms Arjun 1.2k views
0 votes
1 answer
5
What is the time complexity of the following recursive function? int ComputFun(int n) { if(n<=2) return 1; else return (ComputFun(floor(sqrt(n)))+n); } $\Theta(n)$ $\Theta(\log n)$ $\Theta(n\log n)$ $\Theta(\log \log n)$
asked Dec 9, 2020 in Unknown Category gatecse 32 views
0 votes
1 answer
6
If algorithm $A$ and another algorithm $B$ take $\log_2 (n)$ and $\sqrt{n}$ microseconds, respectively, to solve a problem, then the largest size $n$ of a problem these algorithms can solve, respectively, in one second are ______ and ______. $2^{10^n}$ and $10^6$ $2^{10^n}$ and $10^{12}$ $2^{10^n}$ and $6.10^6$ $2^{10^n}$ and $6.10^{12}$
asked Nov 20, 2020 in Algorithms jothee 404 views
0 votes
0 answers
7
The running time of an algorithm is $O(g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n)) \cdot (O= \textit{ big }O)$ its worst-case running time is $\Omega (g(n))$ ... , $(o = \textit{ small } o)$ Choose the correct answer from the options given below: $(a)$ only $(b)$ only $(c)$ only $(d)$ only
asked Nov 20, 2020 in Algorithms jothee 173 views
1 vote
1 answer
8
1 vote
2 answers
9
The most efficient algorithm for finding the number of connected components in a $n$ undirected graph on $n$ vertices and $m$ edges has time complexity $\Theta (n)$ $\Theta (m)$ $\Theta (m+n)$ $\Theta (mn)$
asked Apr 2, 2020 in Algorithms Lakshman Patel RJIT 251 views
0 votes
1 answer
10
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, 2020 in DS Lakshman Patel RJIT 707 views
0 votes
1 answer
11
An algorithm is made up pf two modules $M1$ and $M2.$ If order of $M1$ is $f(n)$ and $M2$ is $g(n)$ then the order of algorithm is $max(f(n),g(n))$ $min(f(n),g(n))$ $f(n) + g(n)$ $f(n) \times g(n)$
asked Apr 1, 2020 in Algorithms Lakshman Patel RJIT 357 views
0 votes
1 answer
12
...