# 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.

## 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

## Related Asymptotic Notations

1. O (Big Oh),
2. Ω (Big omega),
3. ϴ (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.

## Web References:

##### Naveed Tawargeri

Hi Everyone, Naveed Tawargeri Here. I am a graduate of Information Science Engineering and working as Digital Marketing Executive.