Notations of Time and Space Complexity of an Algorithm

• Various types of notations are used to express the time and space complexity of algorithms.
• These notations help to provide a concise and standardized way of describing how the performance of an algorithm scales with input size.
• The most commonly used notations are Big O, Omega, and Theta.

A brief overview:

  Time Complexity Notations:

 1. Big O Notation (O):
   - Definition: Represents the upper bound or worst-case time complexity of an algorithm.
   - Usage: \(O(g(n))\) denotes an upper limit on the growth rate, indicating that the running time of the algorithm will not exceed \(c \cdot g(n)\) for sufficiently large \(n\) (where \(c\) is a positive constant).
 
2. Omega Notation (Ω):
   - Definition: Represents the lower bound or best-case time complexity of an algorithm.
   - Usage: \(\Omega(g(n))\) denotes a lower limit on the growth rate, indicating that the running time of the algorithm will not be less than \(c \cdot g(n)\) for sufficiently large \(n\) (where \(c\) is a positive constant).
 
3. Theta Notation (Θ):
   - Definition: Represents both the upper and lower bounds, providing a tight bound on the growth rate.
   - Usage: \(\Theta(g(n))\) denotes that the running time of the algorithm grows at the same rate as \(g(n)\) for sufficiently large \(n\).
 

 Space Complexity Notations:

 1. Big O Notation (O):
   - Definition: Represents the upper bound or worst-case space complexity of an algorithm.
   - Usage: Similar to time complexity, \(O(g(n))\) denotes an upper limit on the memory space required by the algorithm.
 
2. Omega Notation (Ω):
   - Definition: Represents the lower bound or best-case space complexity of an algorithm.
   - Usage: Similar to time complexity, \(\Omega(g(n))\) denotes a lower limit on the memory space required by the algorithm.
 
3. Theta Notation (Θ):
   - Definition: Represents both the upper and lower bounds on space complexity, providing a tight bound.
   - Usage: Similar to time complexity, \(\Theta(g(n))\) denotes that the memory space required by the algorithm grows at the same rate as \(g(n)\) for sufficiently large \(n\).

 

 Practical Notations:

 1. Little O Notation (o):
   - Definition: Represents an upper bound that is not asymptotically tight.
   - Usage: \(o(g(n))\) denotes that the running time or space complexity of the algorithm grows strictly slower than \(g(n)\).
 
2. Little Omega Notation (ω):
   - Definition: Represents a lower bound that is not asymptotically tight.
   - Usage: \(\omega(g(n))\) denotes that the running time or space complexity of the algorithm grows strictly faster than \(g(n)\).

 

These notations are used in algorithm analysis to describe how the performance of an algorithm scales with the input size.

Big O notation is particularly common and widely used to express the upper bounds of time and space complexity, providing a simplified and understandable representation of an algorithm's efficiency.

-------------------------------------------------