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