edited by
284 views
0 votes
0 votes

Consider the following code snippet. It accepts a positive integer $n$ as input.

int i = 0, j = 0, val = 1;
for(i = 1; i <= n; i++) {
    j = n;
    if (i%2 == 0) {
        while(j>1) {
            val = val * j;
            j = j / 2;  
        }
    }
}

What is the worst-case time complexity of the algorithm?

  1. $O(n)$
  2. $O(n^{2})$
  3. $O(n^{2} \log n)$
  4. $O (n \log n)$
edited by

1 Answer

0 votes
0 votes

for(i=1;i<=n;i++){ ---------------------------loop1

  j=n;

  if(i%2==0)

  while(j>1)      ----------------------------loop2

      {

         j=j/2;

      }

}

Loop1 :runs for 'n' times.

Loop2 : Start with j=n then n/2 then n/4 .........1

So n,n/2,n/4,n/8........1  i.e logn times.

hence Exact Time complexity= 1 + logn + 1 + logn +1 +logn .........

i.e (n/2)*logn + n/2

=(nlogn)/2 

So O(nlogn) Hence D is Correct Option.

Answer:

Related questions

0 votes
0 votes
1 answer
1
admin asked Jan 5, 2019
368 views
An unordered list contains $n$ distinct elements. The number of comparisons to find an element in the list that is larger than the second minimum in the list is$\Theta(n ...
0 votes
0 votes
1 answer
2
admin asked Jan 5, 2019
428 views
Which of the given options provides the increasing order of asymptotic complexity of functions $\text{f}_{1}, \text{f}_{2}, \text{f}_{3}$ and $ \text{f}_{4} $ ?$\text{f}_...
0 votes
0 votes
1 answer
3
admin asked Jan 5, 2019
281 views
The recurrence equation $T(n) = T(\sqrt{n}) + O(1)$ has the following asymptotic solution:$T(n) = O(\sqrt{n})$$T(n) = O(\log n)$$T(n) = O(n^{1/\log n})$$T(n) = O(\log \lo...
0 votes
0 votes
0 answers
4
admin asked Jan 5, 2019
207 views
The Adjacency matrix of a directed graph $\text{G}$ is given below.$\begin{array} {} & a & b & c & d & e & f & g & h & i \\ a & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ b & ...