Time Complexity and Space Complexity

timecomplexity

Time Complexity and Space Complexity

What is time complexity, space complexity, Asymptotic analysis, asymptotic notation, big O notation?

Before reading (time complexity and space complexity) these topics in detail, we try to know one by one what the meanings of these terms actually are.

Time Complexity

Time complexity told the time taken by the algorithm with respect to the input size

Space Complexity

space complexity of an algorithm is overall space taken through the algorithm with respect to the input size. space complexity consists of both Auxiliary space and space utilized by input.

Asymptotic Analysis

Asymptotic analysis is a mathematical way where we computing the running time of any operation.

Using asymptotic analysis we can very well predict an algorithm’s best case, average case, and worst-case scenario.

Usually, the time required by an algorithm falls under three types −

  • Best Case − Minimum time required for program execution.

  • Average Case − Average time required for program execution.

  • Worst Case − Maximum time required for program execution.

1<logn<√n<n<nlogn<n²<n³<…<2^n<n^n

Asymptotic Notation

Following are the commonly used asymptotic notations to calculate the running time complexity of an algorithm.

  • Ο Notation (Big Oh Notation)
  • Ω Notation (Omega Notation)
  • θ Notation (Theta Notation)

Big Oh Notation

Big O

The notation  Ο(n) is the formal way of representing the upper bound of an algorithm’s running time.

It calculates the time complexity of the worst-case scenario or the longest period of time an algorithm could take to complete.

Definition: 

f(n) = O(g(n)) (f is a Big-O of g) or f<= g if there exist constants N and c so that for all n=>N, f(n) <= c.g(n)

Big O really just says that my runtime is sort of bounded above by some multiple of this thing. sometimes you want to say the reverse. sometimes you want to say that I am bounded below. And so there is the different notation for that Omega Notation and Theta Notation respectively.

Omega Notation

Omega time complexity

The notation  Ω(n) is the formal way of representing the lower bound of an algorithm’s running time.

It calculates the time complexity of the best-case scenario or the best amount and the smallest period of time an algorithm could take to complete.

Defination:

For functions f,g : N -> R+ we say that:

f(n) =  Ω(g(n)) or f>=g if for some c, f(n) >= c.g(n)  {f grows no slower than g}

Theta Notation

Theta time complexity

The notation θ (n) is the formal way of representing both the lower bound and the upper bound of an algorithm’s running time.

Defination:

For functions f,g : N -> R+ we say that:

f(n) =  θ(g(n)) or f ~ g if f = O(g) and f = Ω(n)  {f grows same rate as g}

Properties of Asymptotic Notation

General Properties

  • If f(n) is O(g(n)) then a*f(n) is O(g(n))
    • e.g: f(n) = 2n²+5 is O(n²) then 7*f(n) = 14n²+35 is O(n²)

It is applicabla for Θ as well as Ω notation aslo.

Reflexive

  • If f(n) is O(g(n)) and g(n) is O(h(n)) than f(n) = O(h(n))
    • e.g: f(n)=n, g(n)=n²

Transitive

  • If f(n) is O(g(n)) and g(n) is O(h(n))  than f(n) = O(h(n))
    • e.g:  f(n)=n, g(n)=n², h(n)=n³ than n is O(n²) and n² is O(n³) than n is O(n³)

It is supported by all three notations.

Symmetric

  • If f(n) is Θ(g(n)) than g(n) is Θ(f(n))
    • e.g: f(n)=n² and g(n)=n² than
      f(n)=Θ(g(n))=Θ(n²)
      g(n)=Θ(f(n))=Θ(n²)

This is true only case of Θ notation

Transpose Symmetric

  • If f(n)=O(g(n)) than g(n) is Ω(f(n))
    • e.g: f(n)=n, g(n)=n² than 
      n is O(n²) [n is upper bond of n]
      n² is Ω(n) {n² is low erbound of n}

This is true for only Big-O and Ω notations

Others Properties

  • If f(n)=O(g(n)) and f(n)=Ω(g(n)) than f(n)=Θ(g(n))
  • If f(n)=O(g(n)) and d(n)=O(e(n)) than f(n) + d(n) = O( max (g(n),e(n)))
    • e.g: f(n) = n = O(n), d(n) = n² = O(n²) 
      f(n) + d(n) = n + n² = O(n²)
  • If f(n) = O(g(n)) and d(n) = O (e(n)) than f(n) * g(n) = O(g(n) * e(n))
    • e.g: f(n) = n² = O(n²), d(n) = n = O(n)
      f(n) * d(n) = n² * n = n³

Leave a Reply

Your email address will not be published. Required fields are marked *