Explain Big-oh, Omega and theta notation with the help of diagram.
Explain Big-oh, Omega and theta notation with the help of diagram. How do we analyze and measure time complexity of algorithm?
Explain Big-oh, Omega and theta notation with the help of diagram. How do we analyze and measure time complexity of algorithm?
Big-O gives an upper bound, Omega (Ω) a lower bound, and Theta (Θ) a tight bound on how an algorithm's running time grows with input size \(n\).
1. Big-O (upper bound). \(f(n) = O(g(n))\) if there are constants \(c > 0\) and \(n_0\) such that
\[0 \le f(n) \le c\,g(n)\ \text{ for all } n \ge n_0.\]
Diagram: after \(n_0\), the curve of \(f(n)\) always stays below the curve \(c\,g(n)\). Used for worst case. Example: \(3n + 2 = O(n)\) with \(c = 4, n_0 = 2\).
2. Omega (lower bound). \(f(n) = \Omega(g(n))\) if
\[f(n) \ge c\,g(n) \ge 0\ \text{ for all } n \ge n_0.\]
Diagram: after \(n_0\), \(f(n)\) stays above \(c\,g(n)\). Example: \(3n + 2 = \Omega(n)\) with \(c = 3\).
3. Theta (tight bound). \(f(n) = \Theta(g(n))\) if
\[c_1 g(n) \le f(n) \le c_2 g(n)\ \text{ for } n \ge n_0.\]
Diagram: after \(n_0\), \(f(n)\) lies between the two curves \(c_1 g(n)\) and \(c_2 g(n)\), like a sandwich. Example: \(3n + 2 = \Theta(n)\) with \(c_1 = 3, c_2 = 4\).
How time complexity is analysed and measured.
Common growth order: \(1 < \log n < n < n\log n < n^2 < n^3 < 2^n < n!\).
Log in or create a free account to answer this question.