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. 

PCP in AI and Machine Learning

In Partnership with Purdue UniversityExplore Course
PCP in AI and Machine Learning

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)

FREE Machine Learning Certification Course

To become a Machine Learning EngineerExplore Course
FREE Machine Learning Certification Course

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:

  1. Implementation of the program for a particular algorithm.
  2. 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. 

Free Course: Machine Learning Algorithms

Learn the Basics of Machine Learning AlgorithmsEnroll Now
Free Course: Machine Learning Algorithms

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. 

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)

Looking forward to a successful career in AI and Machine learning. Enrol in our Professional Certificate Program in AI and ML in collaboration with Purdue University now.

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 Machine Learning certification training course and be job ready.  

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.