My teacher claimed that this code block will take O(n) time to execute. I'm trying to figure out why. I realize that the two for loops bundled together would be an arithmetic series ..... my logical approach was if K = 3, then the inner loop would run three times, then two times, and then once. If K = 2, then the inner loop would run twice, once, and then stop .

In mathematical terms, it would be N, N-1, N-2 for k = 3

I was later able to use the arithmetic series formula and got N*(N + (N-(N-1))/2..

I don't know how to approach the while loop.

All I can surmise is that when N =4 , the loop runs twice and until N = 9, the loop runs thrice... How would I set this up mathematically?

The end result is N*(N+(N-(N-1)))/2 + O(while loop) to get O(N)?

Any advice would be greatly appreciated.

```
void doit(int n) {
int k = 0; int m = n; int s = 0;
while (m <= n) {
k = k + 1;
m = k * k;
}
for (int i = 0; i < k; i++) {
for (int j = i; j < k; j++) {
s = s + m;
m = m - 1;
}
}
}
```

Well as you can see the while loop and the nested for loop are separate of each other. Therefore we'll calculate the time complexity for each one separately.

## While Loop

Inside the while loop we have instructions that are independent of

`n`

. The problem here is how we calculate the number of times the while loop runs. If we 'cheat' a bit and look at it in terms of`k`

instead of`n`

we notice that at once we exit the loop,`k`

holds the number of times the loop has ran for. It's just like having a counter really. At that point`k^2`

is roughly equal to`n`

therefore the complexity is`O(sqrt(n))`

## For Loops

Here's where the real magic happens as this part will turn out to be

`O(n)`

overcoming the`O(sqrt(n))`

complexity of the while loop.The time taken by each

`for`

loop can be seen as a sum of a constant number of instructions. Therefore we'd have a nested sum. I'll try to describe it for you as StackOverflow won't let me post images. You basically have two sums, one starting with`i=0`

and going up to`(k-1)`

and another starting from`j=1`

and going up to`(k-1)`

and all you're adding is a constant number`c`

of commands.You can easily calculate this sum and it turns out that the complexity is

`O(k^2)`

but again we have to think in terms of`n`

and just like before it becomes`O(n)`

.