DEV Community

Plabon Joseph Costa
Plabon Joseph Costa

Posted on

Big O Time and Space Complexity

What is Big O Notation?

Big O Notation refers to mathematical functions applied in computer science for calculating algorithms time and space complexity. It defines the runtime required for executing an algorithm, but it won’t tell how fast your algorithm’s runtime is. Instead, It will help you identify how your algorithm’s performance will change with the input size. It describes the upper bound nature of an algorithm.

In Big O analysis, it only cares about the code that grows fastest as the input grows, because everything else is eclipsed (Big O analysis is also called asymptotic analysis).

As per the formal definition, we can define O(g(n)) as a set of functions and a function f(n) as a member of that set only if this function satisfy the following condition:
0 <= f(n) <= cg(n)0 <= f(n) <= cg(n)

If an algorithm carries out a computation on each item within an array of size n, that algorithm runs in O(n) time and performs O(1) for each item.

It’s obvious that the runtime grows linearly as the input size grows. Mathematically, it is expressed as T = an + b

For finding the complexity from this equation:

  • Find the fastest growing time
  • Take out the coefficient

Remember in the rules we mentioned Bio O only cares about the part where it grows the fastest? So we find the part (an) and secondly take out the part coefficient (a), we are left with n, and that’s O(n).

Big O notation will be used in two ways:

  • To classify the time complexity(speed) of an algorithm.
  • To classify the space complexity(memory) of an algorithm.

Definition of Big O Notation varies in both Mathematical and Industrial ways. Mathematically it is called Big O and Order of for Industrial.

What is Time and Space Complexity?

The time complexity means the total time taken by an algorithm to execute as a function of input’s length.

Similarly, the space complexity specifies how much space or memory taken by the algorithm. Space Complexity includes both auxiliary space and space used by the input. Auxiliary space is the temporary or extra space used by the algorithm while it is executed.

Both the time and space complexities depend on various factors, such as underlying hardware, OS, CPU, Processor etc. However, whenever we analyze the performance of the algorithm, none of the factors are taken into consideration.

There are three different cases for Time and space complexity:

  • Best case
  • Average case
  • Worst case

The following are some complexities:

  • Constant Time O(1)
  • Logarithmic Time O(logn)
  • Linear Time O(n)
  • Log Linear Time O(nlogn)
  • Quadric Time O(n^2)
  • Exponential Time O(2^n)
  • Factorial Time O(n!)

What is the Bio O Chart?

It is asymptotic notation, allowing you to express the performance of algorithms. Big O helps the programmer to understand the worst-case scenario and the execution time required or the memory used by an algorithm. Big O complexity can be understood with the following graph:

Image description

Resources:

Top comments (0)