Rather than printing characters, make a table.
Code:
#include <stdio.h>
int f(int n)
{
int r = 0;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n*n/i; j+=i)
{
r++;
}
}
return r;
}
int main(void)
{
for ( int n = 1 ; n < 20 ; n++ ) {
int O_n2 = n * n;
printf("f(%2d) = %3d ; O(N^2)=%4d 2*O(N^2)=%4d, 3/2*O(N^2)=%4d\n",
n, f(n), O_n2, 2*O_n2, 3*O_n2/2);
}
return 0;
}
$ gcc bar.c
$ ./a.out
f( 1) = 1 ; O(N^2)= 1 2*O(N^2)= 2, 3/2*O(N^2)= 1
f( 2) = 5 ; O(N^2)= 4 2*O(N^2)= 8, 3/2*O(N^2)= 6
f( 3) = 12 ; O(N^2)= 9 2*O(N^2)= 18, 3/2*O(N^2)= 13
f( 4) = 23 ; O(N^2)= 16 2*O(N^2)= 32, 3/2*O(N^2)= 24
f( 5) = 37 ; O(N^2)= 25 2*O(N^2)= 50, 3/2*O(N^2)= 37
f( 6) = 55 ; O(N^2)= 36 2*O(N^2)= 72, 3/2*O(N^2)= 54
f( 7) = 75 ; O(N^2)= 49 2*O(N^2)= 98, 3/2*O(N^2)= 73
f( 8) = 99 ; O(N^2)= 64 2*O(N^2)= 128, 3/2*O(N^2)= 96
f( 9) = 127 ; O(N^2)= 81 2*O(N^2)= 162, 3/2*O(N^2)= 121
f(10) = 157 ; O(N^2)= 100 2*O(N^2)= 200, 3/2*O(N^2)= 150
f(11) = 192 ; O(N^2)= 121 2*O(N^2)= 242, 3/2*O(N^2)= 181
f(12) = 228 ; O(N^2)= 144 2*O(N^2)= 288, 3/2*O(N^2)= 216
f(13) = 269 ; O(N^2)= 169 2*O(N^2)= 338, 3/2*O(N^2)= 253
f(14) = 313 ; O(N^2)= 196 2*O(N^2)= 392, 3/2*O(N^2)= 294
f(15) = 360 ; O(N^2)= 225 2*O(N^2)= 450, 3/2*O(N^2)= 337
f(16) = 412 ; O(N^2)= 256 2*O(N^2)= 512, 3/2*O(N^2)= 384
f(17) = 463 ; O(N^2)= 289 2*O(N^2)= 578, 3/2*O(N^2)= 433
f(18) = 521 ; O(N^2)= 324 2*O(N^2)= 648, 3/2*O(N^2)= 486
f(19) = 582 ; O(N^2)= 361 2*O(N^2)= 722, 3/2*O(N^2)= 541
You know it's basically going to be O(N^2) because you have two nested loops both involving n.
The actual scale factor (1,2,3/2) doesn't matter, nor do other minor O(N) terms.
For sufficiently large N, the fact is that N^2 will completely dominate any other terms.
Big O notation - Wikipedia