In this chapter, you will learn about the different algorithmic approaches that are usually followed while programming or designing an algorithm. Then you will get the basic idea of what Big-O notation is and how it is used. Finally, there will be brief lists of the different types of algorithmic analysis that is being performed using the types of complexity.
Various Approaches to Algorithmic Design
Any system can have components which have components of their own. Certainly, a system is a hierarchy of components. The highest level of components corresponds to the total system. There are usually two approaches to design such hierarchy:
- Top-down approach
- Bottom-up approach
Now let's discuss both of them:
Top-down approach
The top-down approach starts by identifying the major components of the system or program decomposing them into their lower level components and iterating until the desired level of modular complexity is achieved. The top-down method takes the form of stepwise working and refinement of instructions. Thus the top-down approach starts from an abstract design, and each step is refined into more concrete level until the final refined stage is not reached.
Bottom-up approach
The bottom-up design starts with designing the most basic or primitive components and proceeds to the higher level component. It works with layers of abstraction. Starting from below, the operation that provides a layer of abstraction is implemented. These operations are further used to implement more powerful operations and still higher layers of abstraction until the final stage is reached.
What is Big - O notation?
When resolving a computer-related problem, there will frequently be more than just one solution. These individual solutions will often be in the shape of different algorithms or instructions having different logic, and you will normally want to compare the algorithms to see which one is more proficient. So, this is where Big O analysis helps program developers to give programmers some basis for computing and measuring the efficiency of a specific algorithm.
If f(n) represents the computing time of some algorithm and g(n) represents a known standard function like n, n2, n log n, then to write:
f(n) is O g(n)
which means that f(n) of n equals to the biggest order of the function, i.e., the g(n).
So what Big - O does? It helps to determine the time as well as space complexity of the algorithm. Using Big - O notation, the time taken by the algorithm and the space required to run the algorithm can be ascertained. Some of the lists of common computing times of algorithms in order of performance are as follows:
- O (1)
- O (log n)
- O (n)
- O (nlog n)
- O (n2)
- O (n3)
- O (2n)
Thus algorithm with their computational complexity can be rated as per the mentioned order of performance.
Algorithm Analysis
In the last chapter, you have studied about the time and space complexity. This complexity is used to analyze the algorithm in the data structure. There are various ways of solving a problem and there exists different algorithms which can be designed to solve the problem.
Consequently, analysis of algorithms focuses on the computation of space and time complexity. Here are various types of time complexities which can be analyzed for the algorithm:
- Best case time complexity: The best case time complexity of an algorithm is a measure of the minimum time that the algorithm will require for an input of size 'n.' The running time of many algorithms varies not only for the inputs of different sizes but also for the different inputs of the same size.
- Worst case time Complexity: The worst case time complexity of an algorithm is a measure of the minimum time that the algorithm will require for an input of size 'n.' Therefore, if various algorithms for sorting are taken into account and say 'n,' input data items are supplied in reverse order for a sorting algorithm, then the algorithm will require n2 operations to perform the sort which will correspond to the worst case time complexity of the algorithm.
- Average Time complexity Algorithm: This is the time that the algorithm will require to execute a typical input data of size 'n' is known as the average case time complexity.
