Properties of Big O Notation
Below are some important Properties of Big O Notation:
1. Reflexivity:
For any function f(n), f(n) = O(f(n)).
Example:
f(n) = n2, then f(n) = O(n2).
2. Transitivity:
If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)).
Example:
f(n) = n3, g(n) = n2, h(n) = n4. Then f(n) = O(g(n)) and g(n) = O(h(n)). Therefore, f(n) = O(h(n)).
3. Constant Factor:
For any constant c > 0 and functions f(n) and g(n), if f(n) = O(g(n)), then cf(n) = O(g(n)).
Example:
f(n) = n, g(n) = n2. Then f(n) = O(g(n)). Therefore, 2f(n) = O(g(n)).
4. Sum Rule:
If f(n) = O(g(n)) and h(n) = O(g(n)), then f(n) + h(n) = O(g(n)).
Example:
f(n) = n2, g(n) = n3, h(n) = n4. Then f(n) = O(g(n)) and h(n) = O(g(n)). Therefore, f(n) + h(n) = O(g(n)).
5. Product Rule:
If f(n) = O(g(n)) and h(n) = O(k(n)), then f(n) * h(n) = O(g(n) * k(n)).
Example:
f(n) = n, g(n) = n2, h(n) = n3, k(n) = n4. Then f(n) = O(g(n)) and h(n) = O(k(n)). Therefore, f(n) * h(n) = O(g(n) * k(n)) = O(n5).
6. Composition Rule:
If f(n) = O(g(n)) and g(n) = O(h(n)), then f(g(n)) = O(h(n)).
Example:
f(n) = n2, g(n) = n, h(n) = n3. Then f(n) = O(g(n)) and g(n) = O(h(n)). Therefore, f(g(n)) = O(h(n)) = O(n3).
Big O Notation Tutorial – A Guide to Big O Analysis
Big O notation is a powerful tool used in computer science to describe the time complexity or space complexity of algorithms. It provides a standardized way to compare the efficiency of different algorithms in terms of their worst-case performance. Understanding Big O notation is essential for analyzing and designing efficient algorithms.
In this tutorial, we will cover the basics of Big O notation, its significance, and how to analyze the complexity of algorithms using Big O.
Table of Content
- What is Big-O Notation?
- Definition of Big-O Notation:
- Why is Big O Notation Important?
- Properties of Big O Notation
- Common Big-O Notations
- How to Determine Big O Notation?
- Mathematical Examples of Runtime Analysis
- Algorithmic Examples of Runtime Analysis
- Algorithm Classes with Number of Operations and Execution Time
- Comparison of Big O Notation, Big Ω (Omega) Notation, and Big θ (Theta) Notation
- Frequently Asked Questions about Big O Notation
Contact Us