What is total frequency count and running time (Big-O notation)?

Question

I have the following code snippet:

1. for (i = 1; i < n; i++) 
2.    for (j = 1; j < i*i; j++) 
3.      if(j % i == 0)
4.         for(k = 0; k < j;k++)
5.            sum++; 

What is total frequency count and running time (Big-Oh notation)?

Frequency count examine a piece code and predict the number of instructions to be executed (e.g. for each instruction predict how many times each will be encountered as the code runs.)

I try to analyse in the following way:

Loop1 is executed n-1 times, then F.C. is 2n
Loop2 is executed (i*i)-1 times, then F.C. is 3(i*i)
total frequency count for loop1+loop2 is 2n + sum (from i=1 to n-1)3*i*i
I have a problem with if(j%i==0). What is loop execution here?
Loop4 is executed j times, then F.C. is 2j+2

Answer 1

There's something fishy here:

1. for (i = 1; i < n; i++) 
2.    for (j = 1; j < i*i; j++)      // <-- These two lines.
3.      if(j%i==0)                   // <-- 
4.         for(k=0; k<j;k++)
5.            sum++;

Since We're only executing the loop body when j is a multiple of i, why not count in i's:

1. for (i = 1; i < n; i++) 
2.    for (j = i; j < i*i; j += i) 
3.        for(k=0; k<j;k++)
4.            sum++; 

Which is O(n^4)

Looking at your original algorithm. The first 2 lines do O(n^3) work. Then O(n^2) of the time, (j%i == 0), we do O(n^2) more work. So The algorithm above is O(n^4).

Answer 2

You have a sum:

TimeComplexity =

= Sum_{i=1..n} Sum_{j=1..i^2} (1 + [j % i = 0]*Sum_{k=1..j} 1) =

= Sum_{i=1..n} Sum_{j=1..i^2} (1 + [j % i = 0]*j) =

= Sum_{i=1..n} Sum_{j=1..i^2} 1 + Sum_{i=1..n} Sum_{j=1..i^2} [j % i = 0]*j =

= Sum_{i=1..n} i^2 + Sum_{i=1..n} (i+2i+3i+...+i*i) =

= Sum_{i=1..n} i^2 + Sum_{i=1..n} i(1+2+3+...+i) =

= Sum_{i=1..n} i^2 + Sum_{i=1..n} i^2(i+1)/2 =

= Sum_{i=1..n} (i^3 + O(i^2)) =

= O(n^4).

Enjoy