ISRO CSE 2020 | Question: 36

Question

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?

• A. $O(n^2)$
• B. $O(n\log\ n)$
• C. $O(n)$
• D. $O(n\log\ n\log\ n)$

Comments

Option B is right here because outer loop run logn times(1,2,4,8,…...)so logn

and inner loop runs n times corresponding to each value of i

so TC:nlogn

---

Atleast read question please 🙏

---

Could have formed it like "Which of these is not a valid time complexity/upper bound for this code"

Answer 1

$\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.

Comments

Yes $\mathbf{O(n)}$ is correct.

---

What is meaning of invalid string here?

---

@jeet

what is the meaning of invalid string here I am not getting 

Answer 2

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

Comments

yes this is the actual way to getting odd one out option

 

Answer 3

Option C is correct here 

checking all the options

Answer 4

Outer Loop :

i=1*2 :2

i=2*2 : 2^2

i=2^2*2 : 2^3

i=2^k and outer loop terminates if i>n substituting i=2^k

2^k>n

k=logn

and inner loop runs for n times giving overall timecomplexity as O(nlogn)

Answer 5

Correct answer =>C

Time complexity Tight bound = Θ(nlogn)

option A)  nlogn <= c.n^2 (valid for large n)

option B )   nlogn <= c.nlogn (valid tight bound equal)

option C)   nlogn <=c.n (invalid as nlogn >n)

option D)   nlogn ,<= nlognlogn  (valid for large n)

 

Answer 6

the correct option was c O(n)

we get the time complexity was nlogn and we have to compare with the remaining option ,if we take the frst option was n^2

nlogn<=n^2

nlogn <= n*n // if cancled the one n from the right side

logn <=n we know that n was greater when compare to the logn

in the same way we have to compare to the option c

nlogn <=n

nlogn<=c*n // c is the constant if we cancled the n from the right side we having the constant

we are know that "logn" is greater than the c but in the c option they was given the O(n) so that option c was invalid