# Recent questions tagged time-complexity

1
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}$
2
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
3
1 vote
4
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)$
5
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)$
6
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)$
7
The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by $T(n) = 8T(n/2) + qn,$ if $n>1$ $= p,$ if $n = 1$ Where $p,q$ are constants. The order of this algorithm is $n^{2}$ $n^{n}$ $n^{3}$ $n$
8
The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by $T(n) = 8T(n/2) + qn,$ if $n>1$ $= p,$ if $n = 1$ Where $p,q$ are constants. The order of this algorithm is $n^{2}$ $n^{n}$ $n^{3}$ $n$
9
Consider the following C code segment: int Ls Prime(n) { int i,n; for(i=2;i<=sqrt(n);i++) if(n%i ==0) { printf( NOT Prime.\n ); return 0; } return 1; } Let $T(n)$ denote the number of times the for loop is executed by the program on input $n.$ ... $T(n) = O(\sqrt{n})$ and $T(n) = \Omega (1)$ $T(n) = O(n)$ and $T(n) = \Omega (\sqrt{n})$ None of these
10
An algorithm is made up of two modules $M1$ and $M2.$ If order of $M1$ is $f(n)$ and $M2$ is $g(n)$ then he order of algorithm is $max(f(n),g(n))$ $min(f(n),g(n))$ $f(n) + g(n)$ $f(n) \times g(n)$
11
Which of the following sorting algorithms does not have a worst case running time of $O(n​^2​)$? Insertion sort. Merge sort. Quick sort. Bubble sort.
12
Time complexity of an algorithm $T(n)$, where $n$ is the input size is given by $\begin{array}{ll}T(n) & =T(n-1)+\frac{1}{n}, \text{ if }n>1\\ & =1, \text{ otherwise} \end{array}$ The order of this algorithm is $\log n$ $n$ $n^2$ $n^n$
13
Complexity of Kruskal's algorithm for finding minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is: $O(mn)$ $O(m)$ $O(m+n)$ $O(n)$
14
Two main measures for the efficiency of an algorithm are: Processor and Memory Complexity and Capacity Time and Space Data and Space
15
What is the solution to the recurrence $T(n)=T \bigg (\dfrac{n}{2} \bigg )+n$? $O(\log n)$ $O(n)$ $O(n\log n)$ None of these
16
The concept of order Big O is important because It can be used to decide the best algorithm that solves a given problem It is the lower bound of the growth rate of algorithm It determines the maximum size of a problem that can be solved in a given amount of time Both (A) and (B)
17
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)$
1 vote
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are $\Theta(n \log n),\Theta(n \log n) \text{ and } \Theta(n^2)$ $\Theta(n^2),\Theta(n^2)\text{ and } \Theta(n \log n)$ $\Theta(n^2), \Theta(n \log n)\text{ and } \Theta(n \log n)$ $\Theta(n^2),\Theta(n\log n) \text{ and } \Theta(n^2)$
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}}}$
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)$