Runtime Analysis of Algorithms
In general cases, we mainly used to measure and compare the worst-case theoretical running time complexities of algorithms for the performance analysis.
The fastest possible running time for any algorithm is O(1), commonly referred to as Constant Running Time. In this case, the algorithm always takes the same amount of time to execute, regardless of the input size. This is the ideal runtime for an algorithm, but it’s rarely achievable.
In actual cases, the performance (Runtime) of an algorithm depends on n, that is the size of the input or the number of operations is required for each input item.
The algorithms can be classified as follows from the best-to-worst performance (Running Time Complexity):
- A logarithmic algorithm – O(logn)
Runtime grows logarithmically in proportion to n. - A linear algorithm – O(n)
Runtime grows directly in proportion to n. - A superlinear algorithm – O(nlogn)
Runtime grows in proportion to n. - A polynomial algorithm – O(nc)
Runtime grows quicker than previous all based on n. - A exponential algorithm – O(cn)
Runtime grows even faster than polynomial algorithm based on n. - A factorial algorithm – O(n!)
Runtime grows the fastest and becomes quickly unusable for even
small values of n.
Asymptotic Analysis of Algorithms Notes for GATE Exam [2024]Asymptotic Notations
This Asymptotic Analysis of Algorithms is a critical topic for the GATE (Graduate Aptitude Test in Engineering) exam, especially for candidates in computer science and related fields. This set of notes provides an in-depth understanding of how algorithms behave as input sizes grow and is fundamental for assessing their efficiency. Let’s delve into an introduction for these notes:
Table of Content
- Introduction of Algorithms
- Asymptotic Analysis
- Worst, Best and Average Case
- How to Analyse Loops for Complexity Analysis of Algorithms?
- How to combine the time complexities of consecutive loops?
- Algorithms Cheat Sheet for Complexity Analysis:
- Runtime Analysis of Algorithms:
- Little o and Little omega notations
- What does ‘Space Complexity’ mean?
- Previous Year GATE Questions