# What is the Big O estimate of a nested for loop?

I am trying to figure out what the big o estimate of the following for loop is.

for(int i = 10; i to 100; i++){
for(int j = 1; j to i; j++){
for(int k = 1; k to j; k++){
s=s+i+j;
}
}
}


I was thinking that the two inner loops run n times but I am unsure about the first loop.

What would the Big O estimate be for this code?

## 2 Answers

The whole thing is $O(1)$. This is because the outermost loop has an upper bound of 100 i.e. it is constant, and it bounds the middle loop, which bounds the inner loop. There's a little bit of tricky math to figure out exactly how many times the loop is run, but you can know exactly how many times it is run.

The first hint that this is $O(1)$ is that there are no "free" variables. Pretend the code was linear. What would it be linear in terms of? There are no input parameters. We create $i$,$j$ and $k$, and their values don't change based on some input parameter.

The whole thing has constant running time, since the upper limit of the outer loop is the constant 100 and the inner loops are bounded by the outer loop's value.