# O log n in Data Structures Best Guide

Here is complete Guide on O log n in Data Structures, a very important topic to learn about Asymptotic Notations in Algorithms.

**O log n in Data Structures**

**Big O notation**

- Big O is a mathematical notation describing constraints within any function when it reaches a certain value, or infinite. It’s about infinity.
- Big O are members of a notation group formed by Paul Bachman. The process can be described in computer science by classification based upon ‘running time or space needs’ when input volume increases.
- In analytic number theory big O notation may be used for expressing the boundary between arithmetic function and understanding.
- The letter O is employed in order that growth is called the order of the function.

**Tell me the meaning of O(log n)?**

- Logarithmic running time (O(log n)) means that the running time grows in proportion to the logarithm of the input size.

## Properties

- If f(n) = Θ(g(n)), then there exists positive constants c1, c2, n0 such that 0 ≤ c1.g(n) ≤ f(n) ≤ c2.g(n), for all n ≥ n0
- If f(n) = O(g(n)), then there exists positive constants c, n0 such that 0 ≤ f(n) ≤ c.g(n), for all n ≥ n0
- If f(n) = Ω(g(n)), then there exists positive constants c, n0 such that 0 ≤ c.g(n) ≤ f(n), for all n ≥ n0
- If f(n) = o(g(n)), then there exists positive constants c, n0 such that 0 ≤ f(n) < c.g(n), for all n ≥ n0
- If f(n) = ω(g(n)), then there exists positive constants c, n0 such that 0 ≤ c.g(n) < f(n), for all n ≥ n0

## Orders of common functions

Notation | Meaning |
---|---|

T(n) = O(f(n)) | Asymptotically, T does not grow faster than f. |

T(n) = Omega(f(n)) | Asymptotically, T does not grow slower than f. |

T(n) = Theta(f(n)),when T(n) = O(f(n)) and T(n) = Omega(f(n)) | Asymptotically, T grows equally fast as f. |

T(n) = o(f(n)),means that lim_{n ->infinity}T(n)/f(n)=0 | Asymptotically, T grows slower than f. |

T(n) = omega(f(n)),means that lim_{n ->infinity} T(n)/f(n)=infty. | Asymptotically, T grows faster than f. |

**Table: Standard notations and their meanings**

## Related Asymptotic Notations

**O (Big Oh),****Ω (Big omega),****ϴ (Big theta).**

### Little-o notation

- Little o notation is used to describe
**an upper bound that cannot be tight**.

**Asymptotic Notations:**

- Asymptotic notations are languages that allow us to analyze an algorithm’s running time by identifying its behavior as the input size for the algorithm increases.

### Big Omega Notation:

- Big Omega(Ω) function is
**used in computer science to describe the performance or complexity of an algorithm**. If a running time is Ω(f(n)), then for large enough n, the running time is at least k⋅f(n) for some constant k.

### Other arithmetic operators

Terminology | Meaning |
---|---|

f(n) = O(1) | f is constant. |

f(n) = O(log n) | f is logarithmic. |

f(n) = O(n) | f is linear. |

f(n) = O(n^2) | f is quadratic. |

f(n) = O(n^3) | f is cubic. |

f(n) = O(a^{g(n)}), for some a > 0 and g(n) = omega(log n), sometimes it is understood that g(n) = Omega(n) | f is exponential |

f(n) = O(n^a), for some constant a < infinity | f is polynomial. |

f(n) = o(n) | f is sublinear. |

## Web References:

**Stackoverflow.com**–**O log n in Data Structures**