No. of Step Calculation in an Algorithm

There was a time when the processor were just starting to explore their potential. Then code optimization made a huge difference in the performance of the code. But, today most programmers take the optimization for granted as the compilers are smarter and the processors run like they have fire on their ass. But, to be a good programmer, one should always stick to the roots of programming.

Let their be three arrays, A, B and C of equal lengths n. And an operation is to be performed say,

for(i = 0; i < n; i++)
    A[i] = B[i] + C[i]

Everybody knows that the program is of O(n) complexity. But, what struck me hard is, people say that n statements will be executed for this. This is because, those morons have never been exposed to assembly like programming. This is because of the driver’s mindset, instead of the mechanic’s mindset.

For those who don’t know, your coding language will in turn call the instructions of the processor as:

1. i = 0
2. if i >= n jump to 9
3. x = A[i]
4. y = B[i]
5. z = x + y
6. C[i] = z
7. i = i + 1
8. jump to step 2
9. end

Here, i, x, y, z are values stored in processor registers.

  • Step 3 to 8 can be assumed to be the part of the iteration and will be executed n times.
  • Step 2 will be executed n + 1 times. Last execution will be the step which will allow the jump to step 9. 
  • Thus, total steps required – 6n + n + 1 + 2 = 7n + 3, which of course is O(n)
  • Or, total steps is 2 + n(b + 3) where b is the number of steps in for loop excluding increment of counter and jump.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: