# I want to find the Time Complexity of the following code [duplicate]

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

## marked as duplicate by David Richerby complexity-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 13 '18 at 19:05

• 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. – David Richerby Apr 13 '18 at 19:04

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)$$

• 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. – Mehwish Mustafa Apr 13 '18 at 15:32
• Is this more helpful, I don't see how this is not $O(n^2)$ – someone12321 Apr 13 '18 at 18:52