C++

Forum

 
finding the time complexity

lost110 (140)
Find the worst-case asymptotic time complexity (as a function of n)

1
2
3
4
5
6
7
8
9
10
11
12
 
for(int i =0 ; i < =n ; i++)
{
 for(int j =1; j<= i * i; j++)
{
if (j % i == 0)
{
for(int k = 0; k<j; k++)
 sum++;
}
}
}

So the first for loop has a time complexity of order n .But I am not able to understand the lower loops. Kindly help!
salem c (3685)
> for(int j =1; j<= i * i; j++)
This is O(N2), because you have i*i (which is O(N)).

By themselves, the first two loops are O(N3).

> for(int k = 0; k<j; k++)
This is O(N2), because j.
But what fraction of if (j % i == 0) is actually true for some asymptotic N ?
If it's relatively rare, perhaps it's just O(N).
Perhaps it's very rare, perhaps even log(N).


You can get an idea from doing some tests.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <iostream>

long int worker(int n)
{
  long int sum = 0;
  for (int i = 0; i <= n; i++) {
    for (int j = 1; j <= i * i; j++) {
      if (j % i == 0) {
        for (int k = 0; k < j; k++)
          sum++;
      }
    }
  }
  return sum;
}

int main(int argc, char *argv[])
{
  for (int i = 1; i <= (1 << 10); i <<= 1) {
    std::cout << "i=" << i << ", sum=" << worker(i) << std::endl;
  }
}
jonnin (11331)
This is a nice problem. Here is my 10 cent take on it.

outer loop is n, of course (not my N loop, ignore that).
the next loop is the sum of squares times:
(N * (N + 1) * (2N + 1)) / 6 (this is O(n^3).. its ~ (n*n*n)/3 )
That is the combination of the first 2 loops.

then the weird one.
the k loop happens about n*n/2 times. each time it does, it adds i*i sums.

I think where we end up is O(n^4). Its significantly less than that due to additional terms that are ignored in big-O. I don't know how to deal with the changing i term here (if you wanted it exact).
My final approximation was (N^4)/6 .


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
#include <iostream>

int main()
{
	
int sum = 0;
uint64_t ct = 0;
int n = 100;

for(n = 10; n <= 1000; n+=25)
{
	ct = 0;
for(int i =0 ; i <=n ; i++)
 {
  for(int j =1; j<= i * i; j++)
  {
  if (j % i == 0)
  {
   for(int k = 0; k<j; k++)
    {
     sum++;
	 ct++;
    }
   }
  }
}
 std::cout << n <<" "<< ct << endl;
}

 
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
10 1705
35 205905
60 1711355
85 6783680
110 18860380
135 42550830
160 83636280
185 149069855
210 246976555
235 386653255
260 578568705
285 834363530
310 1166850230
335 1590013180
360 2119008630
385 2770164705
410 3560981405
435 4510130605
460 5637456055
485 6963973380
510 8511870080
535 10304505530
560 12366410980
585 14723289555
610 17402016255
635 20430637955
660 23838373405
685 27655613230
710 31913919930
735 36646027880
760 41885843330
785 47668444405
810 54030081105
835 61008175305
860 68641320755
885 76969283080
910 86032999780
935 95874580230
960 106537305680
985 118065629255

Last edited on
Topic archived. No new replies allowed.