Algorithm is defined as a sequence of finite steps or instructions written in understandable language to solve a specific problem. Algorithm complexity is the mathematical technique of creating efficient algorithms. Most of the times, algorithms are written in simple sentences that are easy to read and follow. Algorithms can also be written in a formal language that reduces the ambiguity of steps. To make the problem solving process efficient the algorithms must display following characteristics.
- Input– the algorithms must indicate the input needs for the solution
- Output– The algorithm must clearly specify the outcomes
- Finiteness– The algorithm must not indicate infinite execution of a program created from the algorithm. The algorithm must define the termination of the process.
- Unambiguity– The statements of the algorithm must be unambiguous means there should be single interpretation of the statements written.
- Definite– The algorithm must display definiteness in statements so that the user can run through the steps to understand the functionality using pen and paper.
Examples of algorithms in real life
- Recipe of a dish
- Instructions to fill a form
- Steps for calculation of Income tax
- Instructions or directions to reach target location
- Install and use a machine
Why Algorithm Complexity?
Algorithm is the first step in creation solution of a given problem. There can be occasions and situations that one problem can be solved in many different ways. To create efficient solution a user must be able to identify the best algorithm that can be converted into a computer program.
Complexity of algorithm helps a user in finding a better solution by evaluation the performance of different algorithms on the basis of the characteristics. Many times the performance can be measured by analysing the time taken to output results, the quality or the simplicity of the designed solution.
Complexity of algorithm gives mathematical techniques of evaluating performance measures and compares the algorithms with ease.
Algorithm design is a step done before coding so it becomes essential to select the most efficient algorithm among the available options. You cannot code algorithm and then select the efficient solution depending on the performance. It’s exactly the reverse. The available algorithms are evaluated on space and time needs to select a better solution. Since coding will involve a number of man hours to produce a program, so it is always a good idea to first select a algorithm and code it later. That’s why Algorithm complexity!!
Components of Complexity
Two components of algorithm complexity are Space and Time. Space is the storage needs of a program and Time is the CPU time requirements of a problem solution.
When measuring the space needs the algorithm is evaluated for the data structures required to store data, the memory requirements of the program while in execution and the size of procedure stack. When measuring the time needs the algorithm is evaluated for the amount of CPU time needed to display the results.
Space and Time Complexity Trade-off
Together space and time algorithm complexity help a user in finding a good algorithm. But there is a trade-off between space and time complexity. If the time of execution has to be reduced the program requires abundant memory space to load all the required functions and modules for faster execution. But if the space is an important factor then the user has to compromise on the time of execution.
Take the case of an online shopping website. One page displays certain products on the basis of the product category selected by the user depending upon the increasing prices of the products. If the product database is on a remote machine, then this can be done by any of these two options:
A: Each time the user selects a product category an SQL query is fired to retrieve the relevant product names and descriptions.
B: Keep the complete list of products and their descriptions in memory and display it every time the product category is selected by the user.
Both the options given here do not give an ideal and effective solution. The solutions have to be evaluated on various parameters:
- The number of products to be displayed
- The transmission time from the database server to the client machine
- The volume of data transmission each time
- The frequency of requests
- The network bandwidth
The solution lies in agreeing to the trade-off between space and time. Whenever the developer has to select a solution with better performance in time of execution, then option B looks better but it needs more memory requirements. When the solution demands less memory space then option A is better but it will definitely slow down the application. This is an ideal example of situation called the space time trade-off which is an important principle in algorithm design and analysis.