Big O Notation in Data Structures: Time and Space Complexity

Big O Notation in Data Structures: Time and Space Complexity

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

Free DSA Course with Certificate (Online)

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 algorithmO(logn) Runtime grows logarithmically in proportion to n.
  • Linear algorithmO(n) Runtime grows directly in proportion to n.
  • Superlinear algorithmO(nlogn) Runtime grows in proportion to n.
  • Polynomial algorithmO(nc) Runtime grows quicker than previous all based on n.
  • Exponential algorithmO(cn) Runtime grows even faster than the polynomial algorithm based on n.
  • Factorial algorithmO(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

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)
Get Details
Angular Certification Course Jul 20 SAT, SUN
Filling Fast
06:00PM to 08:00PM (IST)
Get Details
Azure Master Class Jul 20 SAT, SUN
Filling Fast
03:00PM to 05:00PM (IST)
Get Details
ASP.NET Core Certification Training Jul 28 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
Software Architecture and Design Training Jul 28 SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
.NET Solution Architect Certification Training Jul 28 SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
Azure Developer Certification Training Jul 28 SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
Advanced Full-Stack .NET Developer Certification Training Jul 28 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
Data Structures and Algorithms Training with C# Jul 28 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
Angular Certification Course Aug 11 SAT, SUN
Filling Fast
09:30AM to 11:30AM (IST)
Get Details
ASP.NET Core Project Aug 24 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details

Can't find convenient schedule? Let us know

About Author
Shailendra Chauhan (Microsoft MVP, Founder & CEO at Scholarhat by DotNetTricks)

Shailendra Chauhan is the Founder and CEO at ScholarHat by DotNetTricks which is a brand when it comes to e-Learning. He provides training and consultation over an array of technologies like Cloud, .NET, Angular, React, Node, Microservices, Containers and Mobile Apps development. He has been awarded Microsoft MVP 8th time in a row (2016-2023). He has changed many lives with his writings and unique training programs. He has a number of most sought-after books to his name which has helped job aspirants in cracking tough interviews with ease.
Accept cookies & close this