Blog_Banner_Asset
    Homebreadcumb forward arrow iconBlogbreadcumb forward arrow iconBig Databreadcumb forward arrow iconBig o notation in data structure: Everything to know

Big o notation in data structure: Everything to know

Last updated:
20th Jul, 2022
Views
Read Time
7 Mins
share image icon
In this article
Chevron in toc
View All
Big o notation in data structure: Everything to know

Big O Notation in a data structure is used for determining the efficiency of an algorithm, the amount of time it takes to run the function with the growth of the input, and how well the function scales. Measuring this efficiency can be divided into two parts, namely, space complexity and time complexity. 

Big O notation refers to the mathematical notation that acts as a limiting factor of any function when an argument is more prone to lean towards a specific value or infinity. It belongs to the category of mathematical notations invented by Edmund Landau, Paul Bachmann, and others. Hence, it is collectively termed the Bachmann–Landau notation or the asymptotic notation. 

As per the mathematical deduction, two functions, f(n) and g(n) are defined on a set of positive or real numbers that are not bound. Here, g(n) is strictly positive for every big value of n. It can be written in the following fashion:

f(n) = O(g(n)) in which n tends to infinity (n → ∞)

Ads of upGrad blog

However, here, the supposition of n to infinity is not exclusively defined, and the above expression can therefore be written as:

f(n) = O(g(n))

Here, f and g are the necessary functions that start from positive integers to real numbers that aren’t non-negative.

Hence, large n values are denoted by the Big O asymptotic.

Properties of Big O Notation in Data Structure

The Big O algorithm in data structure has quite a few mandatorily required properties. The said essential properties of the Big O Notation are as follows:

  • 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))
  • Constant Multiplication:
    If f(n) = c.g(n), then O(f(n)) = O(g(n)) in which c is a nonzero constant.
  • Polynomial Function:
    If f(n) = a0 + a1.n + a2.n2 + — + am.nm,
    then O(f(n)) = O(nm).

Learn Software Development Courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs or Masters Programs to fast-track your career.

Explore our Popular Software Engineering Courses

Here, while addressing Big O, every single log function increases similarly.

Importance Of Big O Notation In Runtime Analysis Of Algorithms

The complexities of the worst-case running time of the algorithm are used to draw comparisons and calculate, especially in the case of analyzing the performance of an algorithm. The order of O(1), depicted as the Constant Running Time, is the algorithm’s fastest running time – the time that the algorithm takes is the same for various input sizes. It is important to note that the ideal runtime of an algorithm is the constant running time, which is very rarely achieved because the algorithm’s runtime depends on the input size of n.

For example:

As mentioned above, an algorithm’s runtime performance is majorly dependent on the input size of n. Let us elucidate this fact with a few mathematical examples to make the runtime analysis of an algorithm for various sizes of n:

  • n = 20
    log (20) = 2.996;
    20 = 20;
    20 log (20) = 59.9;
    202 = 400;
    220 = 1084576;
    20! = 2.432902 + 1818;
  • n = 10
    log (10) = 1;
    10 = 10;
    10 log (10) = 10;
    102 = 100;
    210 = 1024;
    10! = 3628800;

The runtime performance of an algorithm is calculated similarly.

Here are a few other algorithmic examples of runtime analysis –

  • When it comes to Linear Search, the runtime complexity is O(n).
  • The runtime complexity is O(log n) for binary search.
  • For Selection Sort, Bubble Sort, Bucket Sort, Insertion Sort, the runtime complexity is O(n^c).
  • When it comes to Exponential algorithms such as Tower of Hanoi, the runtime complexity is O(c^n).
  • For Merge SortSort and Heap Sort, the runtime complexity is O(n log n).

How does Big O analyze space complexity?

Determining both space and runtime complexity for an algorithm is an essential step. This is because we can determine the execution time that an algorithm takes by analyzing the runtime performance of the algorithm and the memory space the algorithm is taking through the analysis of the space complexity of the algorithm. Therefore, to measure the space complexity of an algorithm, we must compare the worst-case space complexity performance of the algorithm.

For determining the space complexity of an algorithm, we must follow these two tasks –

Task 1: It is vital to implement the program for a particular algorithm.

Task 2: It is essential to know the size of the input n to determine the memory each item will hold.

These two essential tasks require to be accomplished before calculating the space complexity for an algorithm.

Examples of Space Complexity Algorithms

There are many examples of algorithms with space complexity, some of which have been mentioned below for a better understanding of this type of algorithm:

  • For Bubble sort,  Linear Search, Selection sort, Insertion sort, Heap sort, and Binary Search, the space complexity is O(1).
  • The space complexity is O(n+k) when it comes to radix sort.
  • The space complexity is O(n) for quick SortSort.
  • The space complexity is O(log n) for merge sort.

Example of Big O Notation in C

It is a fact that Big O notation is primarily used in Computer Science for determining the complexity or performance of an algorithm. This notation provides us with the ability to classify the behavior of algorithms based on the growth of the memory space or execution time requirements when the extent of the input data becomes large. It is not designed to predict the actual memory usage or execution time but for comparing algorithms and then selecting the best amongst them for the job. It is not language-specific but is also implemented in C. 

Below, you will find the selection sort algorithm in C where the worst-case complexity (Big O notation) of the algorithm has been calculated:-

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;  

}  

To analyze the algorithm:

  • It can already be denoted that the range of the for outer loop is i < n, which states that the order of the loop is O(n).
  • Next, we can identify that it is also O(n) as j < n for the inner for loop.
  • The constant is ignored, even if the average efficiency is found n/2 for a constant c. So, the order is O(n).
  • After multiplying the order of the inner loop and the outer loop, the runtime complexity achieved is O(n^2).

Other algorithms in C can be easily implemented, where the complexities can be easily analyzed and determined similarly.

Usage Of Big O Notation

There are two main areas where Big O Notation is applied:-

  • Mathematics: The Big O Notation is quite commonly used in the field of mathematics to describe how a finite series closely approximates a function, especially when it comes to the cases of an asymptotic expansion or truncated Taylor series.
  • Computer science: It is a well-established fact that the Big O notation is mostly used in the field of computer science because of its usefulness in the analysis of algorithms

However, in both applications, the function g(x) appearing within the O(·) is often chosen to be possibly the most simple if lower order terms and constant factors are omitted.

Ads of upGrad blog

There are two other usages of this notation that are formally close but relatively different. They are:-

  • Infinite asymptotics
  • Infinitesimal asymptotics.

However, this distinction is not in principle, in application only with the formal definition for the “Big O” being the exact same for both cases. The only difference is the limits for the argument of the function.

Read our Popular Articles related to Software Development

Conclusion

In conclusion, we can say that Big Data plays an integral role in data structures, and having in-depth, comprehensive knowledge about Big O notation is an excellent skill set to possess. It is in high demand in the job sector and can be potentially a great choice for a career path. upGrad’s Advanced Certificate Programme in Big Data will give you the leverage you need to boost your career. It will introduce you to top professional skills like Data Processing with PySpark, Data Warehousing, MapReduce, Big Data Processing on the AWS Cloud, Real-time Processing, etc.

Profile

Rohit Sharma

Blog Author
Rohit Sharma is the Program Director for the UpGrad-IIIT Bangalore, PG Diploma Data Analytics Program.
Get Free Consultation

Selectcaret down icon
Select Area of interestcaret down icon
Select Work Experiencecaret down icon
By clicking 'Submit' you Agree to  
UpGrad's Terms & Conditions

Our Popular Big Data Course

Frequently Asked Questions (FAQs)

1How does the Big O Notation bind function?

The Big O notation is used for defining an algorithm’s upper bounds thus it binds functions from above.

2How can Big O multiply?

Big O can be multiplied if the time complexities are multiplied.

3What is the difference between Big O and Small O?

Big O is asymptotically tight, whereas the upper bound of Small O is not asymptotically tight.

Explore Free Courses

Suggested Blogs

50 Must Know Big Data Interview Questions and Answers 2024: For Freshers &#038; Experienced
8198
Introduction The demand for potential candidates is increasing rapidly in the big data technologies field. There are plenty of opportunities in this
Read More

by Mohit Soni

Top 6 Major Challenges of Big Data &#038; Simple Solutions To Solve Them
103223
No organization today can operate effectively without data. Data, generated incessantly from various sources like business transactions, sales records
Read More

by Rohit Sharma

17 Jun 2024

13 Best Big Data Project Ideas &#038; Topics for Beginners [2024]
101994
Big Data Project Ideas Big Data is an exciting subject. It helps you find patterns and results you wouldn’t have noticed otherwise. This skill
Read More

by upGrad

29 May 2024

Characteristics of Big Data: Types &#038; 5V&#8217;s
7128
Introduction The world around is changing rapidly, we live a data-driven age now. Data is everywhere, from your social media comments, posts, and lik
Read More

by Rohit Sharma

04 May 2024

Top 10 Hadoop Commands [With Usages]
12366
In this era, with huge chunks of data, it becomes essential to deal with them. The data springing from organizations with growing customers is way lar
Read More

by Rohit Sharma

12 Apr 2024

What is Big Data &#8211; Characteristics, Types, Benefits &#038; Examples
187055
Lately the term ‘Big Data’ has been under the limelight, but not many people know what is big data. Businesses, governmental institutions, HCPs (Healt
Read More

by Abhinav Rai

18 Feb 2024

Cassandra vs MongoDB: Difference Between Cassandra &#038; MongoDB [2023]
5536
Introduction Cassandra and MongoDB are among the most famous NoSQL databases used by large to small enterprises and can be relied upon for scalabilit
Read More

by Rohit Sharma

31 Jan 2024

Be A Big Data Analyst – Skills, Salary &#038; Job Description
899958
In an era dominated by Big Data, one cannot imagine that the skill set and expertise of traditional Data Analysts are enough to handle the complexitie
Read More

by upGrad

16 Dec 2023

12 Exciting Hadoop Project Ideas &#038; Topics For Beginners [2024]
21371
Hadoop Project Ideas & Topics Today, big data technologies power diverse sectors, from banking and finance, IT and telecommunication, to manufact
Read More

by Rohit Sharma

29 Nov 2023

Schedule 1:1 free counsellingTalk to Career Expert
icon
footer sticky close icon