Because here the loops are simple, it's easy to count all actions done.
The a[i] *= 2
is done N
times.
The d[i][j] = a[i] * c[j]
is done:
- when
i==0
: 0 times
- when
i==1
: 1 times
- ...
- when
i==N-1
: N
-1 times.
The total is: N + 0 + 1 + ... + N-1
= N + (N-1)(N-2)/2
= (1/2)(N^2) - N/2 + 1
.
For O()
we consider only the highest power and ignore constant coefficients, here it is O(N^2)
.
Why this? We want to know what happens when N
is big.
E.g: N = 1,000
=> exact number is (1/2)(N^2) - N/2 + 1
= 499,501
.
N = 10,000
=> exact number is (1/2)(N^2) - N/2 + 1
= 49,995,001
.
We see that for N
10 times bigger, result is about 100 times bigger. It is O(N^2)
.
We can do shorter, rereading the code:
There is a loop on N
, and inside a loop limited by i
and i
is varying like N. It is a O(N^2)
process.
i
is not a free parameter but a loop variable. What shouldO(N*i)
complexity mean?