Power of Code optimization

Hi folks, In this content I”ll show you how some simple observations can bring drastic changes in your code’s execution time. I recently learned about this technique of pattern observation from one online course I’m enrolled in.

Let’s take one example —To return count of all the divisors of numbers.

Code without Optimization

For this, Simple solution that would come into our mind is checking it with every elements from 1 to N.

Let’s write down the pseudo code for this.

int count=0;
for(int i=1;i<=N;i++){
  if(N%i==0){
      count++;
  }
}

In the above code if N is divisible by i, count will increase by 1 each time.

Now, we can see that above code will take N number of iterations.

Lets assume, in 1 sec, we can perform 10⁸ iterations.

It means if number N = 10⁸, it will take 1 sec to execute the code. Let’s check some test cases.

If N=10⁸, Iterations = 10⁸, Time = 1 sec.

If N=10⁹, Iterations = 10⁹, Time = 10 sec.

If N=10¹⁸, Iterations = 10¹⁸, Time = 10¹⁰ sec. (10¹⁰ sec = approx 317 years)

In the above scenario, we can see, execution time is increasing linearly as we increasing the input to very large number.

Code with Optimization

Now, let’s consider a number N = 24.

Factors of 24 are-

1,2,3,4,6,8,12,24

We know that the factors occurs with the pairs, i.e

1*24=24, 2*12=24, 3*8=24, 4*6=24, 6*4=24, 8*3=24, 12*2=24, 24*1=24 …statement(1)

In the above statement, we can observe that after certain number, pairs are getting repeated. After 4*6 we are getting same pairs as left hand side

i.e

1*24 is same as 24*1, 2*12 is same as 12*2, and so on….

So if pairs are getting repeated, why to check with all the divisors, instead, we can just find the number after which the pairs are getting repeated.

From the above pairs, we can make an equation like this-

i*j=N, i.e. j=N/i

From the statement(1) we can observe one thing that, when j>i, pairs are getting repeated. From this we can conclude that we can put the codition in for loop like

i≤j

i.e i≤N/i

i.e i*i≤N or i≤sqrt(N)

with each iteration we will increase count by 2 as we are now dealing with 2 divisors(i & j) in each iteration.

Now our pseudo code looks like this-

int count=0;
for(int i=1;i*i<=N;i++){
  if(N%i==0){
      count=count+2;
  }
}

Now let’s check the test cases

if N=10⁸, iterations=sqrt(10⁸)=10⁴, Time=1/10⁴ sec

if N=10⁹, iterations=sqrt(10⁹)=10^4.5, Time=1/(10^3.6) sec

if N=10¹⁸, iterations=sqrt(10¹⁸)=10⁹, Time=10 sec

Now scroll up and compare these test cases with unoptimized solution.

without optimization, for N=10¹⁸, Time is 10¹⁰ sec which is approx 317 years

and for optimized code, for N=10¹⁸, Time is just 10 sec.

So this is the amount of change we can bring to our code by optimization using simple observations in the patterns of input/output.