For each integer 0 <= i <= n, there's another loop which goes 0 <= j <= i.
So, the i-th integer requires i calls to foo2()
.
Over n integers, this adds up to an average of (n / 2) extra calls to foo2()
per integer -
n + (n - 1) + ... + 1 + 0
is the same as
n + (n - 1 + 1) + ... + (n - n/2 + n/2)
, or
n * (n / 2)
.
Since the upper bound on complexity is n^2 / 2,
its growth will happen as quickly as n^2
- so the complexity is O(n^2)
.