0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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