# Big O Notation in Data Structures: Time and Space Complexity

06 Jun 2024
Beginner
2.49K Views
Learn via Video Course & by Doing Hands-on Labs

## 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. For more information and understanding, consider our Best Dsa Courseprogram.

## Big O Runtime Analysis of the Algorithm

We saw this mathematical representation of Big O notation in the previous tutorial
``````O(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
``````
Now, we will see the general step-by-step process for `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)`, then `O(f(n)) = O(g(n))`; where c is a nonzero constant.
• Polynomial Function: If `f(n) = a0 + a1.n + a2.n2 + —- + am.nm`, then `O(f(n)) = O(nm)`.
• 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) = logan` and `g(n)=logbn`, then `O(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

## 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 Data Structures Certificationprogram. It will benefit you a lot.

## FAQs

### Q1. On which parameter does performance of an algorithm depends?

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.

### Q2. Space complexity depends on which factors?

• Program implementation for a specific algorithm.
• The input size or the amount of storage required for each item.

Share Article

### Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
 Generative AI For Software Developers Jul 20 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST) Angular Certification Course Jul 20 SAT, SUN Filling Fast 06:00PM to 08:00PM (IST) Azure Master Class Jul 20 SAT, SUN Filling Fast 03:00PM to 05:00PM (IST) ASP.NET Core Certification Training Jul 28 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST) Software Architecture and Design Training Jul 28 SAT, SUN Filling Fast 05:30PM to 07:30PM (IST) .NET Solution Architect Certification Training Jul 28 SAT, SUN Filling Fast 05:30PM to 07:30PM (IST) Azure Developer Certification Training Jul 28 SAT, SUN Filling Fast 10:00AM to 12:00PM (IST) Advanced Full-Stack .NET Developer Certification Training Jul 28 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST) Data Structures and Algorithms Training with C# Jul 28 SAT, SUN Filling Fast 08:30PM to 10:30PM (IST) Angular Certification Course Aug 11 SAT, SUN Filling Fast 09:30AM to 11:30AM (IST) ASP.NET Core Project Aug 24 SAT, SUN Filling Fast 07:00AM to 09:00AM (IST)

Can't find convenient schedule? Let us know

Similar Articles