[Algorithm] Fundamental

Geeks for Geeks

Geeks for Geeks

Linear vs Binary Search

Linear vs Binary

BigO

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).
Explanation: This property states that a function is always an upper bound of itself. In other words, the growth rate of f(n) is at most proportional to itself.

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)).
Explanation: This property allows us to chain inequalities. If one function is bounded by another, and that second function is bounded by a third, then the first function is bounded by the third.

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)).
Explanation: Multiplying a function by a constant factor does not change its growth rate in Big O terms.

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)).
Explanation: When adding two functions, the one with the higher growth rate dominates.

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(n6).
Explanation: The product of two functions' growth rates is the product of their individual growth rates.

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).
Explanation: When composing functions, the outer function's growth rate is determined by the inner function's growth rate.