Big O Notation in Data Structures: An Overview
In the previous tutorial on Complexity Analysis, we saw the three asymptotic notations used to denote time and space complexities.In this DSA tutorial, we will discuss the analysis of the algorithm using the most commonly used Big O asymptotic notation in complete detail. Mastering DSA can unlock roles with up to $15,000 higher annual pay. Join our Free DSA Course today!
Big O Runtime Analysis of the Algorithm
We saw this mathematical representation of Big O notation in the previous tutorialO(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
Big O runtime analysis- Determine the input and what n stands for.
- Describe the algorithm's highest limit of operations in terms of n.
- Remove all but the terms with the highest order.
- Eliminate all the consistent factors.
Features of Big O notation analysis
- Constant Multiplication: If
f(n) = c.g(n), thenO(f(n)) = O(g(n)); where c is a nonzero constant. - Polynomial Function: If
f(n) = a0 + a1.n + a2.n2 + —- + am.nm, thenO(f(n)) = O(nm). - Summation Function: If
f(n) = f1(n) + f2(n) + —- + fm(n)andfi(n)≤fi+1(n) ∀ i=1, 2, —-, m, thenO(f(n)) = O(max(f1(n), f2(n), —-, fm(n))). - Logarithmic Function: If
f(n) = loganandg(n)=logbn, thenO(f(n))=O(g(n)); all log functions grow in the same manner in terms of Big O.
Runtime Analysis of Algorithms
The performance of an algorithm depends on n i.e. the size of the input or the number of operations required for each input item.The algorithms can be classified from the best-to-worst performance (Running Time Complexity):
- Logarithmic algorithm –
O(logn)Runtime grows logarithmically in proportion to n. - Linear algorithm –
O(n)Runtime grows directly in proportion to n. - Superlinear algorithm –
O(nlogn)Runtime grows in proportion to n. - Polynomial algorithm –
O(nc)Runtime grows quicker than previous all based on n. - Exponential algorithm –
O(cn)Runtime grows even faster than the polynomial algorithm based on n. - Factorial algorithm –
O(n!)Runtime grows the fastest and becomes quickly unusable for even small values of n.
Read More - Data Structure Interview Questions for Experienced
Examples of algorithms with high runtime complexity i.e worst-case scenario
- Linear Search:
O (n) - Binary Search:
O (log n) - Bubble sorting, insertion sorting, selection sorting, and bucket sorting:
O(nc) - Exponential algorithms like the Tower of Hanoi:
O(cn) - Heap Sort and Merge Sort:
O (n log n)
Big O Space Complexity Analysis of Algorithms
For performance analysis of an algorithm, not only time complexity needs to be considered but also the memory usage amount of the program. We need to measure and compare the worst-case theoretical space complexities of algorithms.Functions are categorized using the Big O notation according to how quickly they expand; many functions with the same rate of growth could be written using the same notation. Since a function's order is also referred to as its development rate, the symbol O is used. A function's development rate is typically only constrained by the upper bound in a large O notation representation of the function.
Space complexity analysis depends on two major factors
- Program implementation for a specific algorithm.
- The input size or the amount of storage required for each item.
Examples of some Algorithms Space Complexity
- Linear search, binary search, bubble sort, selection sort, heap sort, and insertion sort:
O(1) - Radix sort:
O(n+k) - Quick sort:
O(n) - Merge Sort:
O (log n)
Summary
Big O Notation is particularly helpful in understanding algorithms while working with big data. It helps programmers determine the scalability of an algorithm or count the steps necessary to produce outputs based on the data the program utilizes. If you want to go to a level above, enroll in our Free DSA Course With Certificate program. It will benefit you a lot.Average Java Solution Architect earns ₹35–45 LPA. Don’t let your career stall at ₹8–10 LPA—Enroll now in our Java Architect Course to fast-track your growth.
