🎯 The Core Idea

Big-O notation describes how an algorithm's performance scales as input size grows.

⚠️ Key Rules

• 1️⃣
  Count Iterations, NOT Time

  Execution time varies by machine. Iterations are consistent.

• 2️⃣
  Ignore Constants

  O(2n) → O(n), O(100) → O(1)

• 3️⃣
  Keep Only the Highest Order Term

  O(n² + n + 100) → O(n²)

🏆 Why Big-O for Competitions?

In coding competitions, we care about the worst case because:

• Test cases include maximum input sizes (N up to 10⁶ or more)
• We need to ensure our solution doesn't exceed time limits
• Big-O gives us the upper bound on operations

🍎 The Apple vs Orange Analogy

📊 Mathematical Proof

📊 Comparing 5n, 2n, and 6n

When n = 100:

🎯 The Key Insight

Big-O describes the shape of growth, not the exact count.

• 5n grows linearly → O(n)
• 100n grows linearly → O(n)
• 0.001n grows linearly → O(n)

Constants only affect the speed, not the scalability.

📊 Finding the Crossover

💾 Memory Usage of Data Types

📊 Example Calculation

int n;              // 4 bytes
int arr[n];         // n × 4 bytes
int sum = 0;        // 4 bytes

Total = 4 + 4n + 4 = 4n + 8 bytes
Space Complexity = O(n)

📊 Operations Per Second

A typical judge can execute ~10⁸ operations/second

⚠️ Dangerous Example

int a = 1000000000;  // 10⁹
int b = 1000000000;  // 10⁹
int c = a * b;       // 10¹⁸ - OVERFLOW!

// Result: c = garbage value!
// Expected: 1000000000000000000
// Actual: Some random negative number!