Theoretical time complexity calculation of nested dependent for loops

Question

How do I calculate the big-O time complexity of the following nested for loop with dependent indices:

void function1 (int n)
{
     int x = 0;
     for (int i = 0; i <= n/2; i+=3)
        for (int j = i; j <= n/4; j+=2)
           x++;
}

Answer 1

Complexity of the code is defined as how many times your code will be executed for a given n.
There are two ways to do it.

1. Simulation: Run the code for different value of n and find out the values. In this case this is equivalent to the final value of x.
2. Theoretical:
   

Let's first check for each i how many times your code runs:
Using the arithmetic progression formula (a_n = a_1 + (k-1)*d):

• i=0 => n/4 = 0 + (k-1)*2 => n/8 + 1 times
• i=3 => n/4 = 3 + (k-1)*2 => (n-12)/8 + 1 times
• i=6 => n/4 = 6 + (k-1)*2 => (n-24)/8 + 1 times
• i=9 => n/4 = 9 + (k-1)*2 => (n-36)/8 + 1 times
  
  Let's check the last i's now:
• i=n/4 => n/4 = n/4 + (k-1)*2 => 1 times
• i=n/4 - 3 => n/4 = (n/4-3) + (k-1)*2 => 3/2 + 1 times
• i=n/4 - 6 => n/4 = (n/4-6) + (k-1)*2 => 6/2 + 1 times

So total number of times inner loop will be running is:

= (1) + (3/2 + 1) + (6/2 + 1) + (9/2 + 1) ...  + ((n-12)/8 + 1)+ (n/8 + 1)
=> (0/2 + 1) + (3/2 + 1) + (6/2 + 1) + (9/2 + 1) ...  + ((n-12)/8 + 1)+ (n/8 + 1)

Can be written as:

=> (0/2 + 3/2 + 6/2 + ... (n-12)/8 + n/8) + (1 + 1 + 1 ... 1 + 1)

Let's assume there are total P terms in the series:
Let's find out P:

n/8 = (0/2) + (P-1)*(3/2)   =>   P = (n+12)/12

Now summing up the above series:

= [(P/2) (0/2 + (P-1) * 3/2)] + [P]
= P(3P+1)/4
= (n+12)(3(n+12)+12)/(4*12*12)
= (n^2 + 28n + 96)/192

So the final complexity of the code is

= (number of operation in each iteration) * (n^2 + 28n + 96)/192

Now look at the term (n^2 + 28n + 96)/192 For a very large n this will be close to ~n^2

Following is the complexity comparison:
Linear scale was difficult to analyse to I plotted log scale. Though for small n you don't see the complexity converging to n^2.