Big O notation does not give you the number of operations. It just tells you how fast it will grow with growing input. And this is what you observe.
When you increased input c
times, the total number of operations grows c^2
.
If you calculated (nearly) exact number of operations precisely you would get (n^2)/4
.
Of course you can calculate it with sums, but since I dunno how to use math on SO I will give an "empirical" explanation. Simple loop-within-a-loop with the same start and end conditions gives n^2
. Such loop produces a matrix of all possible combinations for "i"
and "j"
. So if start is 1
and end is N
in both cases you get N*N
combinations (or iterations effectively).
However, yours inner loop is for i < j
. This basically makes a triangle out of this square, that is the 1st 0.5
factor, and then you skip every other element, this is another 0.5
factor; multiplied you get 1/4.
And O(0.25 * n^2) = O(n^2)
. Sometimes people like to leave the factor in there because it lets you compare two algorithms with the same complexity. But it does not change the ratio of growth in respect to n
.