Big O Notation is one of the most necessary mathematical notations used in computer science to measure an algorithm's efficiency. We can analyze how efficient an algorithm is from the amount of time, storage, other resources it takes to run the algorithm, and a change in the input size. Big O Notation in Data Structure tells us how well an algorithm will perform in a particular situation. In other words, it gives an algorithm's upper-bound runtime or worst-case complexity.
An Introduction to Asymptotic Notations
The performance of an algorithm can change with a change in the input size. That is where Asymptotic Notations like Big O Notation comes into play. Asymptotic Notations can describe an algorithm's run time when the input tends toward a specific or limiting value. Asymptotic analysis helps to analyze the algorithm performance change in the order of input size.
What is Big O Notation in Data Structure?
Big O Notation in Data Structure is used to express algorithmic complexity using algebraic terms. It describes the upper bound of an algorithm's runtime and calculates the time and amount of memory needed to execute the algorithm for an input value.
Mathematical Definition
Consider the functions f(n) and g(n), where functions f and g are defined on an unbounded set of positive real numbers. g(n) is strictly positive for every large value of n.
The function f is said to be O(g) (read as big- oh of g), if, for a constant c>0 and a natural number n0, f (n) ≤ CG(n) for all n >= n0
This can be written as:
f(n) = O(g(n)), where n tends to infinity (n → ∞)
We can simply write the above expression as:
f(n) = O(g(n))
Properties of Big O Notation
The most important properties of Big O Notation in Data Structure are:
-
Constant Multiplication:
If f(n) = CG(n), then O(f(n)) = O(g(n)) for a constant c > 0
-
Summation Function:
If f(n) = f1(n) + f2(n) + -- + FM(n) and fi(n)≤ fi+1(n) ∀ i=1, 2, --, m,
then O(f(n)) = O(max(f1(n), f2(n), --, fm(n)))
-
Logarithmic Function:
If f(n) = log an and g(n)=log bn, then
O(f(n)) = O(g(n))
-
Polynomial Function:
If f(n) = a0 + a1.n + a2.n2 + -- + am.nm, then
O(f(n)) = O(nm)
How Does Big O Notation Make a Runtime Analysis of an Algorithm?
In order to analyze and calculate an algorithm's performance, we must calculate and compare the worst-case runtime complexities of the algorithm. The order of O(1) - known as the Constant Running Time - is the fastest running time for an algorithm, with the time taken by the algorithm being equal for different input sizes. Although the Constant Running Time is the ideal runtime for an algorithm, it can be rarely achieved because the runtime depends on the size of n inputted.
For example, runtime analysis of an algorithm for a size of n = 20:
n=20,
log (20) = 2.996
20 = 20
20 log (20) = 59.9
20^2 = 400
2^20 = 1084576
20! = 2.432902 + 1818
- Runtime complexity of some common algorithmic examples:
- Runtime Complexity for Linear Search – O(n)
- Runtime Complexity for Binary Search – O(log n)
- Runtime Complexity for Bubble Sort, Insertion Sort, Selection Sort, Bucket Sort - O(n^c).
- Runtime Complexity for Exponential algorithms like Tower of Hanoi - O(c^n).
- Runtime Complexity for Heap Sort, Merge Sort - O(n log n).
How Does Big O Notation Analyze Space Complexity?
It is also essential to determine the Space Complexity of an algorithm. This is because space complexity indicates how much memory space the algorithm occupies. We compare the worst-case space complexities of the algorithm.
Before the Big O notation analyzes the Space complexity, the following tasks need to be implemented:
- Implementation of the program for a particular algorithm.
- The size of input n needs to be known to calculate the memory each item will hold.
Space Complexities of some common algorithms:
Linear Search, Binary Search, Bubble sort, Selection sort, Heap sort, Insertion sort - Space Complexity is O(1).
- Radix sort - Space complexity is O(n+k).
- Quick Sort - Space complexity is O(n).
- Merge sort - Space complexity is O(log n).
Example of Big O Notation in C
Implementation of Selection Sort algorithm in C to find worst-case complexity (Big O Notation) of the algorithm:
for(int i=0; i<n; i++)
{
int min = i;
for(int j=i; j<n; j++)
{
if(array[j]<array[min])
min=j;
}
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
Explanation:
The range of the first (outer) for loop is i<n, meaning the order of the loop is O(n).
The range for the second (inner) for loop is j<n; so, the order of the loop is again O(n).
Average efficiency is calculated as n/2 for a constant c, but we ignore the constant. Thus, the order comes to be O(n).
We get runtime complexity by multiplying the inner and outer loop order. It is O(n^2).
In this way, you can implement other algorithms in C, and analyze and determine the complexities.
Our Learners Also Asked
1. What is Big O notation? Give some examples.
In computer science, Big O Notation is a fundamental tool used to find out the time complexity of algorithms. Big O Notation allows programmers to classify algorithms depending on how their run time or space requirements vary as the input size varies.
Examples:
- Runtime Complexity for Linear Search – O(n)
- Runtime Complexity for Binary Search – O(log n)
- Runtime Complexity for Bubble Sort, Selection Sort, Insertion Sort, Bucket Sort - O(n^c).
- Runtime Complexity for Exponential algorithms like Tower of Hanoi - O(c^n).
- Runtime Complexity for Heap Sort, Merge Sort - O(n log n).
2. Why is Big O notation used?
Big O Notation gives the upper-bound runtime or worst-case complexity of an algorithm. It analyzes and classifies algorithms depending on their run time or space requirements.
3. What are time complexity and Big O notation?
Time complexity refers to the amount of time an algorithm takes to run when the input tends towards a specific or limiting value. It calculates the time taken to execute each code statement in an algorithm.
Big O Notation is a tool used to describe the time complexity of algorithms. It calculates the time taken to run an algorithm as the input grows. In other words, it calculates the worst-case time complexity of an algorithm.
Big O Notation in Data Structure describes the upper bound of an algorithm's runtime. It calculates the time and amount of memory needed to execute the algorithm for an input value.
4. What is the other name for Big O notation?
Big O Notation is a mathematical notation named after the term "order of the function", meaning growth of functions. It is also called Landau's Symbol and belongs to the Asymptotic Notations group.
Join The Fastest Growing Tech Industry Today!
Professional Certificate Program in AI and MLExplore Program
5. What are the rules of using Big O notation?
The main rules of Big O Notation in Data Structure are:
- Consider the functions f(n) and g(n), where both functions f and g are defined on an unbounded set of positive real numbers. g(n) is strictly positive for every large value of n.
The function f is said to be O(g) (read as big- oh of g), if, for a constant c>0 and a natural number n0, f (n) ≤ CG(n) for all n >= n0
This can be written as:
f(n) = O(g(n)), where n tends to infinity (n → ∞)
We can simply write the above expression as:
f(n) = O(g(n))
The algorithm’s total performance is f(n) = O(g(n) + f(n))
- Constant Multiplication:
If f(n) = CG(n), then O(f(n)) = O(g(n)) for a constant c > 0
- Summation Function:
If f(n) = f1(n) + f2(n) + -- + FM(n) and fi(n)≤ fi+1(n) ∀ i=1, 2, --, m,
then O(f(n)) = O(max(f1(n), f2(n), --, fm(n)))
- Logarithmic Function:
If f(n) = log an and g(n)=log bn, then
O(f(n)) = O(g(n))
- Polynomial Function:
If f(n) = a0 + a1.n + a2.n2 + -- + am.nm, then
O(f(n)) = O(nm)
Learn from the best in the AI/ML industry with our Caltech Post Graduate Program in AI & ML! Enroll now to get started!
Conclusion
If you work with big data, Big O Notation is especially useful in analyzing algorithms. The tool helps programmers calculate the scalability of an algorithm or count how many steps it must execute to give output based on data the program works on. If you're looking to fine-tune your code to increase efficiency, the Big O Notation in Data Structure can be very effective. For more details on Big O Notation or coding, get started with our AI and ML certification course and be job ready.
