Skip to content
Home » order arithmetic

order arithmetic

📘 Order Arithmetic (Order of Growth)

1️⃣ Introduction

Order arithmetic refers to the rules used to perform mathematical operations (addition, multiplication, comparison, etc.) on asymptotic notations such as:

  • Big-O (O)
  • Omega (Ω)
  • Theta (Θ)

It helps us simplify and compare algorithm complexities and determine the dominant term.

2️⃣ Why Order Arithmetic is Important

Order arithmetic is used to:

  • Simplify time complexity expressions
  • Remove insignificant terms
  • Identify dominant growth rate
  • Compare efficiency of algorithms
  • Write final complexity in standard form

📌 Example:

T(n) = 3n² + 5n + 10
Final Order = O(n²)

3️⃣ Basic Rules of Order Arithmetic

🔹 Rule 1: Ignoring Constants

Constant factors do not affect the order of growth.

📌 Example:

O(2n) = O(n)
O(100n²) = O(n²)

✔ Reason: Growth rate remains same for large n.

🔹 Rule 2: Dominant Term Rule

When multiple terms exist, only the highest-order term is considered.

📌 Example:

O(n³ + n² + n) = O(n³)
O(n log n + n) = O(n log n)

✔ Lower-order terms grow slower and are ignored.

4️⃣ Arithmetic Operations on Orders

🔹 1. Addition Rule

When two functions are added, the maximum order dominates.

📌 Rule:

O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

📌 Examples:

O(n) + O(n²) = O(n²)
O(n log n) + O(n) = O(n log n)

✔ Used when algorithms execute sequentially.

🔹 2. Multiplication Rule

When two functions are multiplied, their orders are multiplied.

📌 Rule:

O(f(n)) × O(g(n)) = O(f(n) × g(n))

📌 Examples:

O(n) × O(n) = O(n²)
O(n) × O(log n) = O(n log n)

✔ Used in nested loops.

🔹 3. Constant Addition

Adding a constant does not change the order.

📌 Example:

O(n) + O(1) = O(n)
O(log n) + O(1) = O(log n)

5️⃣ Order Arithmetic with Loops

🔹 Single Loop

for i = 1 to n
   statement

Order = O(n)

🔹 Nested Loops

for i = 1 to n
   for j = 1 to n
      statement

Order = O(n × n) = O(n²)

🔹 Nested Loops with Different Ranges

for i = 1 to n
   for j = 1 to log n
      statement

Order = O(n log n)

6️⃣ Order Arithmetic with Conditionals

🔹 If–Else

  • Take the maximum order of all branches.

📌 Example:

if condition
   O(n)
else
   O(n²)

Final Order = O(n²)

✔ Worst-case is always considered.

7️⃣ Order Arithmetic with Recursion

🔹 Example

T(n) = T(n/2) + O(1)

Order = O(log n)

T(n) = 2T(n/2) + O(n)

Order = O(n log n)

✔ Used heavily in Divide & Conquer algorithms.

8️⃣ Order Arithmetic with Asymptotic Notations

🔹 Big-O Arithmetic

O(n) + O(n) = O(n)
O(n) × O(n) = O(n²)

🔹 Theta Arithmetic

Θ(n) + Θ(n) = Θ(n)
Θ(n) × Θ(n) = Θ(n²)

🔹 Omega Arithmetic

Ω(n) + Ω(n²) = Ω(n²)

9️⃣ Common Order Hierarchy (Very Important for Exams)

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

✔ Lower order = more efficient algorithm

🔟 Example: Applying Order Arithmetic

Given:

T(n) = 5n² + 10n + 50

Step 1: Ignore constants

n² + n + 1

Step 2: Select dominant term

n²

Final Order:

O(n²)

11️⃣ Exam-Oriented Key Points

  • Always ignore constants
  • Always choose highest-order term
  • Worst case is preferred
  • Used in:
    • Loop analysis
    • Recursive algorithms
    • Algorithm comparison

🔚 Conclusion

Order arithmetic simplifies complex time complexity expressions and helps in identifying the true growth behavior of an algorithm.

Order arithmetic focuses on growth rate, not exact execution time.