0 votes 0 votes 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. Algorithms time-complexity + – Siddharth Bhardawaj asked Aug 5, 2018 • edited Aug 5, 2018 by srestha Siddharth Bhardawaj 1.9k views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Soumya29 commented Aug 5, 2018 reply Follow Share It's $O(n)$ only. After $1^{st}$ iteration of while loop value of $j$ becomes $n$ and it's not getting reset again. 2 votes 2 votes Siddharth Bhardawaj commented Aug 5, 2018 reply Follow Share Thanks though..I made silly mistakes in reading question. 0 votes 0 votes srestha commented Aug 5, 2018 reply Follow Share 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? 1 votes 1 votes Soumya29 commented Aug 5, 2018 reply Follow Share @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. 2 votes 2 votes srestha commented Aug 5, 2018 reply Follow Share yes, thank u :) 0 votes 0 votes Soumya29 commented Aug 5, 2018 reply Follow Share @Srestha, If inner $for \ loop$ run from 0 to $n^2$, then what would be the answer according to you? 0 votes 0 votes srestha commented Aug 5, 2018 reply Follow Share $O(n^{2})$ though while loop will work upto $(n-1)$only 1 votes 1 votes srestha commented Aug 5, 2018 reply Follow Share See @Soumya if it is return value answer will be different https://gateoverflow.in/1542/gate2013-31 0 votes 0 votes Na462 commented Aug 5, 2018 reply Follow Share @ Soumya 3 votes 3 votes srestha commented Aug 5, 2018 reply Follow Share @Na462 absolutely :) 1 votes 1 votes Soumya29 commented Aug 5, 2018 reply Follow Share @Na462 @srestha Yes, It's $O(n^2)$ :) 2 votes 2 votes srestha commented Aug 18, 2018 reply Follow Share @Soumya here TC of j is O(1) right? 0 votes 0 votes nephron commented Oct 31, 2018 reply Follow Share 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(n2) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes o(n²) is correct Psy Duck answered Nov 7, 2022 Psy Duck comment Share Follow See all 0 reply Please log in or register to add a comment.