Thread: Time complexity problem

Originally Posted by Ofir112

Hey, the time complexity here is n^2 . Can someone explain why and how to calculate it? Thanks in advance.

Code:

void f(int n)
{
   for (int i=1; i<=n; i++)
      for (int j=1; j<=n*n/i; j+=i)
          printf(“*”);
}

I don't see that this has anything to do with "time". Not sure what you are attempting to do here.

In the future, please provide a complete program that can be compiled and tested. Compare my version below to better explain what the code is doing:

Code:

#include <stdio.h>

void f(int n)
{
  for (int i=1; i<=n; i++)
  {
    for (int j=1; j<=n*n/i; j+=i)
    {
      printf("*"); // putchar('*'); would be better
    }
    putchar('\n');
  }

}

int main(void)
{
  f(5);

  return 0;
}

Output:

Code:

*************************
******
***
**
*

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