3

Would the following code be O(n^2) or O(n)?

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

Since the inner while loop only runs once from 0 to n I would imagine it's equivalent to having two separate while loops thus the total run-time would be O(2n).

1
  • 2
    It is surely O(n) as constants can be ignored. And your explanation is correct.
    – ygbgames
    Commented Mar 3, 2019 at 6:43

1 Answer 1

3

It is O(n) in this particular pieces of code . Eg If n=10 for i=0 inner loop executes from j=0 to j=9(10 times ) and for i = 1 to 9 inner loop exeutes 0 times , (since j(10) >n(10) will never become true), So total time = 10 times outer + 10 times inner = 20= 2n Hence time complexity is O(n)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.