Overall Big-O complexity of a while loop, with inner step that increases with every loop

Question

I am beginning to learn complexity analysis and I can't figure out the overall Big-O complexity of this part of the algorithm, how should this be calculated?

Code Fragment               Time Complexity
1 -  C = 0                  O(1)
2 -  while C <= L           O(L)
3 -      f(C += 1)          O(???)

Step 3 in fact takes more steps, but can be summarized as a function f that takes C steps to execute.

My problem is that C is increased with every iteration, so any help or direction on that would be appreciated.

Answer 1

Let's plug a few numbers there and see what happens.

• For L=0, step 3 runs once with 0 steps;
• For L=1, step 3 runs twice with 0, and then 1 steps;
• For L=2, step 3 runs 3 times with 0, 1, and 2 steps;
• For L=3, step 3 runs 4 times with 0, 1, 2, and 3 steps;
  [...]
• For L=C, step 3 runs n times with 0, 1, ..., and C=L steps.

Let's say "zero steps" is constant time and change it to 1. So there are two ways to answer this:

• Your function runs 1+1+2+3+..+L steps. That's 1 + a series of L elements that sums to 1 + L * (L + 1) / 2, so it's O(L²);
• It runs L times a function that can be bounded to O(L), so it's O(L²).

Answer 2

If function f() DOESN'T change C ... then the overall complexity of the three lines you showed is O(N): The time will increase linearly as the size of L - C grows. Neither line 1 nor line 3 contribute: they are both essentially "constant".

If function f() DOES change C (e.g. using a global variable), then BOTH lines 2 and 3 contribute, and cjungel's and giusti's answers are correct O(L^2).

Here is a great article:

https://justin.abrah.ms/computer-science/how-to-calculate-big-o.html

Answer 3

If f(C) takes C steps and C increases in every iteration up to the value L then the algorithm is O(L^2).