Introduction of Algorithms
The word Algorithm means “A set of rules to be followed in calculations or other problem-solving operations” Or “A procedure for solving a mathematical problem in a finite number of steps that frequently involves recursive operations “.
Therefore Algorithm refers to a sequence of finite steps to solve a particular problem. Algorithms can be simple and complex depending on what you want to achieve.
Types of Algorithms:
- Brute Force Algorithm
- Recursive Algorithm
- Backtracking Algorithm
- Searching Algorithm
- Sorting Algorithm
- Hashing Algorithm
- Divide and Conquer Algorithm
- Greedy Algorithm
- Dynamic Programming Algorithm
- Randomized Algorithm
In mathematics, asymptotic analysis, also known as asymptotics, is a method of describing the limiting behavior of a function. In computing, asymptotic analysis of an algorithm refers to defining the mathematical boundation of its run-time performance based on the input size. For example, the running time of one operation is computed as f(n), and maybe for another operation, it is computed as g(n2). This means the first operation running time will increase linearly with the increase in n and the running time of the second operation will increase exponentially when n increases. Similarly, the running time of both operations will be nearly the same if n is small in value.
Usually, the analysis of an algorithm is done based on three cases:
- Best Case (Omega Notation (Ω))
- Average Case (Theta Notation (Θ))
- Worst Case (O Notation(O))
Asymptotic Notation |
Symbol |
Definition |
Graph Representation |
---|---|---|---|
Omega Notation |
Ω |
f(n) = Ω(g(n)), If there are positive constants n0 and c such that, to the right of n0 the f(n) always lies on or above c*g(n). |
|
Theta Notation |
Θ |
f(n) = Θ(g(n)), If there are positive constants n0 and c such that, to the right of n0 the f(n) always lies on or above c1*g(n) and below c2*g(n). |
|
Big-O Notation |
O |
f(n) = O(g(n)), If there are positive constants n0 and c such that, to the right of n0 the f(n) always lies on or below c*g(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