Study of Algorithm and its analysis

In the world of computer science, every on heard of the term Algorithm. Now it's the time to know in-depth about it and also study to how to start writing an algorithm before actual coding. Writing an algorithm for a solution is 80% of the coding done. An algorithm is named for the ninth century Persian mathematician al-Khowarizmi, that is it is a set of rules used to compute some calculations. For any computer problems after understanding the problem, writing an algorithm is the second step. Once you have the algorithm ready now you can write code in any programming language you want. The famous algorithm, Euclid's algorithm for getting the greatest common divisor of two numbers is been written in ancient Greek.

 Algorithm: 

"An algorithm is defined as a set of unambiguous rules written in a specific sequence to produce expected output for predefined inputs." Let's come out of this bookies definition, and understand the steps for solving a problem in the world of computers.

Algorithm Approach

Above are the steps to solve a problem in the computers world. In this blog, we will focus on Writing an Algorithm. Now let's discuss the properties of an algorithm. The below properties are nothing but the basic requirement for writing an algorithm.

1. Easily Understandable (Non-ambiguous): Since the algorithm is not the actual code to be run on a machine it should be clear. The algorithm is to be written in proper English language and need not make it complex by using technical terms.
2. Input values: Some argue that mentioning the input values are not necessary for an algorithm but some of the algorithms are designed to work for a range of values and the algorithm may misbehave for some other range of values, so it is a better practice to mention the range of inputs for an algorithm.
3. Diversified (Multiple Form): an algorithm can be written in different forms. Sometimes we write it in proper English language or sometimes we write it in pseudo-code form.  Sometimes a search algorithm can be written in different forms as we have various ways to search but all these forms are accepted. Remember that even all the writing forms are accepted but before writing an algorithm one should always take care of the end user or the client. If the client is a non-technical man then it should always be written in the English language.  
4. Efficiency: An algorithm is the main idea behind the solution so it should always be written with the consideration of efficiency. You can try many times and should select the efficient one.
5. Finiteness: Writing an algorithm doesn't mean to run for infinite times. It should terminate at some point. Always take care of this property in the case of loops and  Recursive algorithms

Designing an Algorithm:

Now it's time to look at the steps to write an algorithm. Below are the steps:

• Understanding the problem
• Decision making on various factors of device
• Algorithm specification
• Verifying the algorithms
• Time and space complexity analysis

Designning an Algorithm

Problem Understanding:  

This step for problem understanding is diffrent that of the 'understanding problem' of the first image. In this step, we will gather all the requirement for writing an algorithm. We need to find out necessary inputs for finding out the expected output. This step helps us to get the range of inputs.

Decision making: 

Now we have the input range and now its time to analyse the constraints for implementing the algorithm. There can be many problems (constraints) for our algorithm to work. We have to find out this constraint.

1. Device compatibility: Measuring this constraint is optional if the algorithm and data values are not on the large scale. But if you are implementing an algorithm similar which need more computation time then thinking on device compatibility is should be our prior concern. Problem-solving on 'BlockChain' kind of problems or 'Image Processing' really need more computation power. In such case either we increase our machines computation power or search for an alternate machine but it happens very rarely. For device point of view, we classify an algorithm into two parts as 'Sequential' and 'Parallel' algorithms. In sequential algorithms, the steps work one after the other since they have the dependency, wherein the case of parallel algorithm two or more task can run simultaneously since no such dependency present. 
2. Data Structure: Choice of the proper data structure is required before actual implementation. Sometimes an algorithm can be done with the help of a 'Hash' rather use of two 'Arrays'. This is an important step since bad selection can lead you to the worst performing algorithm. 
3. Algorithm Strategy: It is a process of selecting an approach for working the algorithm. There are diffrent approach such as,

•  Brute Force: Straightforward technique such as linear searching an element in an array
• Divide-and-Conquer: in this approach, a big problem is divided into n number of smaller problems
• Dynamic programming: The result of smaller, reoccurring instances are obtained to solve the problem
• Greedy approach: To solve a problem for local optimal value. Since it looks for local optimum and terminates as soon as reaching local optima hence its name is 'Greedy'
• Backtracking: As the name suggests we do try and error and backtracking with the error so as to improve the efficiency in the next iteration.

Design of an Algorithm: 

This is the brain of the algorithm designing process. In this step, we write the algorithm in the form of 'pseudo-code' or 'instruction steps in English' or can also draw a flow chart as can show in below diagram.

Designing an Algorithm

Now let's write down a pseudo-code for the above function (summation):

As till now we go through various steps for writing an algorithm now we have our algorithm ready so, it is the time to validate our algorithm and also analyse the same. The verification is simply mean to check the output of the algorithm for various input and expected output combination. Remember this is the algorithm, not our end code, so we have to validate it by manual calculations and assumptions.

Analysis of Algorithm:

 Analysing an algorithm is the final step for writing an algorithm process. In this step, we will be going to analyse its efficiency by measuring,

• Time efficiency
• Space efficiency (memory consumption)
• Logic complexity

Time Complexity: Time efficiency means the total time taken by the algorithm in mini seconds for computation purpose. By time efficiency we can tell whether the algorithm is fast or slow. Each algorithm have three complexity values, these three notations for time complexity measures, 

O, Ω, and Θ

The difference can be found here, Three-time complexity notations. Basically 'O' denotes the possible maximum time, Omega notation denotes an average amount and theta denotes possible minimum time can be taken for an algorithm. In detail, on this is explained below in the same post.

Space Complexity: It means that how much memory taken by the algorithm.

So we completed the topic of Algorithm introduction, Algorithm property and also process for writing an algorithm. Now its time to explore more on Time complexity part of the topic 'Analysis of Algorithm'.

  

Time Complexity:

Time complexity is nothing but the amount of time taken by the computer to run the completion. See it is difficult to calculate the time efficiency by count-down timer since there are many factors which could affect the reading. These factors are such as, the

• load on the system
• Processer type and its efficiency
• Other programs in execution

Hence, we measure them in three notations as mentioned above. Now look at the Order of Growth, The below table shows some time complexity rate for different cases with respect to the rate of input size.

Time Complexity

As, the first row is the time complexities and their corresponding columns shows their order of growth based on the increase in the input size.

The 'n', 'log n', 'n log n' are all nothing but the time complexity. Let's understand it by the example below,

a = [1,2,3,4,5] ,lets assume its size as 'n'

b = [10,100,1000,10000,100000] ,lets assume its size as 'm'

for all values of a (n times)

     for each values of b (m times)

          do some operation

     end of inner for loop

end of the outer for loop

As in the above program, each time of 'n' complete 'm' items will be executed. For the simplicity assume 'm' is equal to 'n'. Then the time complexity for the above program will be (n x n == n^2). So the time complexity for above program is (n^2). Note: '^' is denoting the power notation.

Ok! so we are done for this blog. Hope! you understand the Algorithm topic well and please comment for any doubt regarding time complexity.

Are you are interested in Data Structure.
See my all posts Shubham Mishra

Ok great, we are done with this post,  

Now if you like my way of talk, lets explore more blogs written by me and my inner knowledge,

Get to know answers for common search on Google : A blog for posts which can help you for daily life problems, such as where to get free images, Topic suggestion for the blog.

Computer Science algorithms and other knowledge share : A blog for posts such as best search algorithm, Top interview questions for diffrent technologies, knowledge share for some frameworks or programming languages for the interview or in general terms.

My ideas to solve real world problems : A blog where me shared and presented my ideas to solve a real world problems, this will be interesting for me.

Future of computer science technology discussed : A blog where me discussed about the future of computer science and new technologies which will change our way for looking to solve problems.

Ruby on Rails Web development Blog : As the name suggest, it is the blog for sharing few knowledge about RoR web development framework.

Liked my blogs, wanna to connect:

LinkedIn  |  GitHub  |  HackerEarth  |  ResearchGate  |  Twitter  |  Facebook  |  StackOverflow

Thanks for reading this post, Have a good day :)

<- Naive String Matching algorithm 

Radix sort algorithm -> 

Divide and Conquer technique ->