Analysis of Algorithms and Big O
Why analyze anything really?
There are always different paths available to reach a destination, alternate ways to accomplish the same task and different set of steps to solve the same problem. The question arises, which of these paths or a set of steps is the best choice in a particular scenario. In other words, given a few circumstances, which solution or steps solve the problem while consuming less energy, time and space (or money too).
The choice is usually, not so simple though.
Sometimes we need a balance/tradeoff when it comes to the resources a solution consumes (time, space, energy etc). A particular solution may be the fastest but it may consume a lot of space or energy. Another solution may consume the least space and use very little energy but may be the slowest. Such scenarios require some tradeoffs and may require a balanced solution which may not be the best but does the work in a reasonable time using reasonable resources.
What is an algorithm?
Algorithm is quite simply, the steps involved to solve a problem. As discussed above and as in the real physical world, there can be more than one set of steps to solve a problem.
That means, there could be more than one algorithm for any problem at hand. Say, we need to sort an array of integers in an ascending order. We could sort them using various methods invented in the history of mathematics and computer science. Most common are, bubble sort, merge sort etc.
+------------------+ +-----------+ | | +----------+ | Input | | Algorithm to | | Sorted | |(set of 10 +---------------> + sort numbers +--------------> + Numbers | | numbers) | | | +----------+ +-----------+ +------------------+ [Size of input = 10]
How do I select an algorithm to solve my problem then?
It is quite simple actually. Every problem comes with its environmental limitations (constraints would be a better word).
All we need to do is answer the below questions:
Given the constraints of the environment in which my problem exists
- which solution(algorithm) completes execution in a reasonable amount of time
- uses a reasonable amount of space (ephemeral and persistent memory)
- how does the algorithm perform for varying sizes of the inputs to the problem. Note that an algorithm may perform great with a particular set of inputs but may have degraded performance when the input set increases to a large size
While there could more factors than time and space which could affect the selection of a particular algorithm, time and space are the most common and usually enough to evaluate an algorithm.
Analyzing algorithms for efficiency in the computer world
Coming to the world of computer science, let us dig in to the following factors which directly affect the selection of a algorithm:
- Size of input
- Nature of input
- An algorithm’s execution time is, as it says, how much time does the algorithm take to solve a problem for a particular set of inputs. The key here is, for a particular set of inputs. An algorithm, may or may not complete execution in the same time for all sizes of the inputs.
- Space is defined as the amount of memory required by an algorithm to solve a problem. Some algorithm may require lesser memory for computations to solve a problem, when compared to other algorithms and hence be marked as more efficient. Just like the time resource, space usage by an algorithm is also dependent on the size of the inputs for a particular problem.
- Size of input
- An algorithms performance is in most of the cases proportional to the size of the inputs it is working on. For example, an algorithm may take much longer to sort a billion integers in ascending order as compared to the time taken to sort, say just ten integers. In addition, some algorithms may perform better on a large input set instead of a smaller set of inputs.
What does it tell? It is important that the algorithms performance should be analyzed in the context of the input size it works upon.
- Nature of input
- Another important factor to consider when analyzing the algorithms is the nature of input on which the algorithm is acting upon. For example, some sorting algorithm are substantially faster with mostly sorted data as compared to totally unsorted data. The thing to note here is that the nature of the input provided to the algorithm directly affects the algorithm’s execution time and space requirements.
How to select Which algorithm is better to solve a problem?
When more than one way (algorithm) exists to solve the same problem (which is the case for almost all problems), we need a way to be able to compare these algorithms and select the best option suited for a problem.
However, there is no single and straight way to be able to compare the algorithms. That is because, as described in the above section, an algorithm’s performance is based on various factors. The nature of input, the size of the input etc. all play a role in the performance of the algorithm.
Given the above factors, one way is to measure the algorithm’s performances for three scenarios.
- best case performance
- With the best matching nature of input, optimum size of input, how is the algorithm’s performance. This is denoted by Ω (Big Omega) symbol.
- average case performance
- What would be the average case performance of the algorithm. This is denoted by Θ (Theta) symbol.
- worst case performance
- How does the algorithm perform with the worst possible nature or size of the input values on which it acts. This is denoted by O (Big O) symbol.