Approach for data structure and algorithm

We all might have thought at least once that, is DS & Algo really required. It is quite ironic to see that though we give so much importance to learning DS & Algo concepts we hardly use them and above all, we have no clue how much it can save our resources and help us deliver well-optimized code. Even though I was in the same dilemma for quite some time but when I realized its potential it not only helped me write efficient code but rather it also changed my approach to looking into a problem. So let me take you through one simple problem statement and let’s see how much of an impact an optimized code can have.

Let’s assume that we have to write code to count the factors of a given number, it sounds quite simple, right? Let us write down the code:

function countFactors(N) {
  let count = 0;
  for (let i = 1; i <= N; i++) {
    if (N % i === 0) {
      count = count + 1;
    }
  }
  return count;
}

All we have to do is iterate from 1 to N and check with every value of i that N/i gives the remainder as 0 and count those occurrences. This code will work perfectly fine with small inputs but what will happen if the input size is big? Let’s do some calculations and see how this code is being executed.

Let us assume that 1 operation = 1/10⁸ sec and let’s consider that the loop is taking 1 operation (just an assumption for simplicity)

Let us take N = 10⁹ N operations = 10⁹ * 1 / 10⁸ sec = 10 sec

Let us take N = 10⁹
operations = 10⁹ * 1 / 10⁸ sec 
           = 10 sec

Looks quite good, right? now let’s increase the value of N

Let us take N = 10¹⁸ 

N operations = 10¹⁸ * 1/10⁸ sec 
             = 10¹⁰ sec 

Let's calculate in terms of years 

1 day = 86400 sec 
1 year = 365 days = 365 * 86400 sec 

Therefore, 
N operations = 10¹⁰ sec 
             = 10¹⁰ / (365 * 86400) years 
             = 317 years (approx.)

Now, this looks alarming, if finding the factors of a number will take you 317 years then something is seriously wrong with the approach or else you need to change your profession as you are not gonna get the result in this lifetime.

Let us see what we can do about this to get the result in a short time.

Let's get the factor for 12

1 x 12
2 x 6
3 x 4
4 x 3
6 x 2
12 x 1

I x J = N

If we observe carefully we can make a few deductions:

Factors occur in pairs (Ex: 2 x 6 where both are the factors)
After a given point the factors are repeating
Factors start repeating when I is greater than J

To confirm our deductions let’s try the same with other inputs:

I x J = N
J = N / I

For the factors to repeat I >= J

Therefore, 
   I >= J
   I >= N / I
   I x I >= N
   I >= sqrt(N)

As you can see we just need to find the factors between [1 — sqrt(N)]

Let’s write the code with this logic and see the difference

function countFactors(N) {
  let count = 0;
  for (let i = 1; i <= Math.sqrt(N); i++) {
    if (N % i === 0) {
      if (i === Math.sqrt(N)) {
        count = count + 1;
      } else {
        count = count + 2;
      }
    }
  }
  return count;
}

Looks much better, now let’s pass a large value to this and see how much time would it take to compute the result?

Let us take N = 10¹⁸ 

N operations = sqrt(10¹⁸) * 1/10⁸ sec 
             = 10⁹ * 1/10⁸ sec 
             = 10 sec

Wow!!! This is quite an improvement from 317 years to 10 sec. Now we might not have to change our profession. This is the main reason why DS & Algo are very important to write efficiently as they can save you a lot of resources and time thus giving you a good user experience. Hope the problem statement and the solution were quite clear to help you understand the use of techniques like DS & Algo.

Stay tuned for more content on DS & Algo.

Please share it with others if you found it helpful. 😉

Are Data Structure and Algorithms really necessary?