Pseudocode, and Performance Analysis

Pseudocode

Algorithm is a set of instructions written before the actual code is produced. A code is not the identical representation of the algorithm. It comes in the form of instructions which indeed resembles a programming language. It is known as the pseudocode. For an example let’s look at the pseudocode of linear search:

Algorithm linearSearch(A, n, t) 
// A is an array of size n, and t is the key to find
{
      for i:= 0 to n-1 do {
            if(A[i] := t)then
                  break;
      }
      if(i>n)then
         return -1;
      else
         return i;
}

The above pseudocode shows that a target value (t) is searched through an array (A) of size n.

Performance Analysis

The designed algorithm should be able to answer few questions, such as,

  • Does it solve the problem?
  • Cost of the solution in terms of time, and space.

In this discussion I will solely emphasize on the time, and space complexity.

Time Complexity

We can define time complexity of an algorithm is so many different ways, but in a few words, it is determined by the steps it takes to compute the function. In the above example we see that there is one iteration cycle to search through an array of size n. If we represent this in a form of asymptotic notation, it is O(n) the time complexity of this algorithm. It means that, for a data set of size n, it will iterate n times.

Space Complexity

Space complexity depends on the amount of space an algorithm needs to accomplish the computation. If an algorithm needs a fixed amount of memory to compute a task then the space complexity of that algorithm is constant, Sp = O(1). On the other hand, ignoring the constant variables we find that, the input size is n in the above mentioned pseudocode. And the algorithm is iterating till the last value of n; therefore, the space complexity of this algorithm is, Sp = O(n).

Now, if we want to make it a precise calculation then we have to take the constant parts into consideration. Each variable needs 2 bytes space in the memory. After calculating both constant, and auxiliary parts we get,

2*n bytes for the array A[] 
2 bytes for the variable i
2 bytes for the return keyword
Therefore, it will take (2n + 4) bytes memory for the algorithm to 
complete its execution.

 

Author: ashiquechowdhury

A software developer, and a data science enthusiast

Leave a Reply

Please log in using one of these methods to post your comment:

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