Time complexity

Question

What is  the time complexity of the following code?
 

int j = 0;
for(i=0;i<n;i++)
    {
    for(i=0;i<2n;i++)
        {
        while(j<n)  
            {
              j++;
            }
        }
    }

a) O(n$^{4}$)

b) O(n$^{3}$)

c) O(n$^{2}$)

d) O(n)

I am getting option O(n$^{2}$)  and answer is given O(n)

Explain briefly.

Comments

It's $O(n)$ only. After $1^{st}$ iteration of while loop value of $j$ becomes $n$ and it's not getting reset again.

---

Thanks though..I made silly mistakes in reading question.

---

Here both for loop is taking i only ,right?

then i will increment only 1 time , i.e. inside 2nd for loop upto 2n

and also while will be checking condition upto j=(n-1)

So, maximum time complexity will be for 2nd for loop i.e. $O(2n)=O(n)$

right @Soumya?

---

@Srestha, Absolutely correct.
After last $2^{nd}$ line, I think it as only for $i=0, O(n)$ amount of work is done. For rest of the values of $i,  \text{i.e from 1 to 2n-1, some constant amount}$ of work is done.

---

yes, thank u :)

---

@Srestha, If inner $for \ loop$ run from 0 to $n^2$, then what would be the answer according to you?

---

$O(n^{2})$

though while loop will work upto $(n-1)$only

---

See @Soumya

if it is return value answer will be different

https://gateoverflow.in/1542/gate2013-31

---

@ Soumya

 

---

@Na462 absolutely :)

---

@Na462 @srestha Yes, It's $O(n^2)$ :)

---

@Soumya

here TC of j is O(1) right?

---

 srestha  Soumya29 

Both of them are taking variable 'i' but it is not a global variable. It is local within its scope. So, the complexity should be O(n²)

Answer 1

o(n²) is correct