1. ## Time complexity problem

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(*);
￼}``` 2. 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:
```*************************
******
***
**
*``` 3. 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 Popular pages Recent additions advance, complexity, i=1;, time, void 