-2
$\begingroup$

This question already has an answer here:

Here Nested loops are used, the time complexity of outer loop will be O(n) but how to calculate the complexity of inner loop as it depends on the value of i Here Nested loops are used, the time complexity of outer loop will be O(n) but how to calculate the complexity of inner loop as it depends on the value of i

$\endgroup$

marked as duplicate by David Richerby complexity-theory Apr 13 '18 at 19:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Please don't use images for text: they're inaccessible to search engines and visually impaired people. you can typeset code by putting four spaces in front of each line. $\endgroup$ – David Richerby Apr 13 '18 at 19:04
1
$\begingroup$

Both inner and outer loop are $O(n)$, and the total time complexity is $O(n^2)$. This is because the inner loop will make at most $2*n$ steps which is clearly $O(n)$.

The loop will make $$2\cdot1 + 2\cdot 2 + 2\cdot 3 + 2\cdot 4 + \dots + 2 \cdot n = \\ 2(1 + 2 + \dots + n) = \\ 2(\frac{n\cdot(n+1)}{2}) = \\n \cdot (n+1) = O(n^2)$$

$\endgroup$
  • $\begingroup$ Thanks for sharing your answer. I was also assuming it as n^2 but my tutor has given the hint that it's answer is not O(n^2), that's why I am a bit confused about this. More mathematical explanation will help me to understand it clearly. $\endgroup$ – Mehwish Mustafa Apr 13 '18 at 15:32
  • $\begingroup$ Is this more helpful, I don't see how this is not $O(n^2)$ $\endgroup$ – someone12321 Apr 13 '18 at 18:52

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