edited by
8,563 views
10 votes
10 votes

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?

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

3 Answers

6 votes
6 votes

$\underline{\textbf{Answer:}\Rightarrow}\;\mathbf{c.}$

Outer loop runs $\mathbf{\log n}$ times and inner loop runs $\mathbf{n}$ times.

$\therefore $ The time complexity will be: $\mathbf{O(n\log n)}$

They asked for the invalid string.

So, it will be $\mathbf{O(n)}$

$\underline{\underline{\color{red}{\textbf{Note:}}}}$ Question was $\color{green}{\textbf{excluded}}$ from the evaluation due to ambiguity.

edited by
1 votes
1 votes
The first loop runs for "log" time.

Second loop runs for "nahi" time.

Overall running complexity (as loop is inside the loop ,so their run time complexity gets multiplied )= O(nlogn).

So, the desired complexity is O(nlogn) , therefore the run time complexity can be greater than this but can never be lesser than this.

But according to question, Options A,B and D are correct and C is wrong . (we've to find out the wrong option ).

 

Hence correct answer is C
Answer:

Related questions

3 votes
3 votes
3 answers
1
5 votes
5 votes
2 answers
2
Satbir asked Jan 13, 2020
4,532 views
Huffman tree is constructed for the following data :$\{A,B,C,D,E\}$ with frequency $\{0.17,0.11,0.24,0.33\ \text{and} \ 0.15 \}$ respectively. $100\ 00\ 01101$ is decoded...
5 votes
5 votes
5 answers
3
Satbir asked Jan 13, 2020
7,673 views
If an array $A$ contains the items $10,4,7,23,67,12$ and $5$ in that order, what will be the resultant array $A$ after third pass of insertion sort?$67,12,10,5,4,7,23$$4,...
7 votes
7 votes
2 answers
4
Satbir asked Jan 13, 2020
3,173 views
In linear hashing, if blocking factor $bfr$, loading factor $i$ and file buckets $N$ are known, the number of records will be$cr= i+bfr+N$$r=i-bfr-N$$r=i+bfr-N$$r=i ^{\as...