Algorithm Showdown

Shiksha, Deepak, and Sagar solved a coding assignment. Each used a different approach, and then Shiksha asked:

Shiksha: “We solved the same problem in three different ways, but which one is the best?”

Deepak: “Which one will be faster?”

Sagar: “Faster? Do you mean runtime?”

---

⚡ Why Not Runtime?

Shiksha: “But runtime can’t be tracked easily. Most of our code runs in under 1 second.”

Sagar: “Yes, plus runtime depends on many external factors:”

• Machine configuration (16GB RAM vs 8GB RAM)

• Number of background processes

• Input size

Deepak: So if runtime depends on all these factors, then how do we decide which algorithm is actually better?

Sagar: That’s why we use time and space complexity instead. Lets see.

---

⏳ Time Complexity

📌 Definition:
Time complexity is the mathematical way to express how the number of operations in an algorithm grows with input size n.

📘 How to Calculate Time Complexity

Sagar explains:

✅ 1. Counting Operations

int sum(vector<int>& arr) {
    int s = 0;        // O(1)
    for(int x : arr)  // O(n)
        s += x;       // O(n)
    return s;         // O(1)
}
// Total = O(1 + n + n + 1) → O(n)

✅ 2. Loop Analysis

• One loop → O(n)

• Nested loops → Multiply them → O(n²)

• Sequential loops → Add them → O(n + n²) = O(n²)

✅ 3. Logarithmic Loops

for(int i=1; i<n; i*=2) { } // O(log n)

✅ 4. Recursion

• Write recurrence → Solve it.

• Example: Merge Sort → T(n) = 2T(n/2) + O(n) → O(n log n)

✅ 5. Ignoring Constants

• O(3n + 5) = O(n)

• O(n² + n + 10) = O(n²)

---

💾 Space Complexity

📌 Definition:
Space complexity is the total memory used by an algorithm (variables, input, recursion stack, data structures).

📘 How to Calculate Space Complexity

✅ 1. Variables → Primitive variables take O(1).
✅ 2. Data Structures → Array of size n → O(n), Matrix n×n → O(n²).
✅ 3. Recursion Stack → Depth = n → O(n).
✅ 4. DP / Caching → Storing results increases memory (e.g., Fibonacci DP → O(n), LCS → O(n²)).
✅ 5. Take Maximum → Use the largest memory usage at once.

---

🔎 Example 1: Searching in an Array

Linear Search (O(n))

bool linearSearch(vector<int>& arr, int target) {
    for (int x : arr) {
        if (x == target) return true;
    }
    return false;
}

• Time: O(n)

• Space: O(1)

Binary Search (O(log n)) – array must be sorted

bool binarySearch(vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return true;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

• Time: O(log n)

• Space: O(1)

📌 Dry Run (Binary Search)
Array: [2, 5, 7, 12, 15, 20, 25], Search = 15

1. Mid = 3 → arr[3] = 12 → search right

2. Mid = 5 → arr[5] = 20 → search left

3. Mid = 4 → arr[4] = 15 → ✅ Found

---

🌀 Example 2: Recursive Fibonacci

int fibonacci(int n) {
    if(n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

• Time: T(n) = T(n-1) + T(n-2) + O(1) → O(2^n)

• Space: Recursion depth = n → O(n)

---

📊 Comparison Table

---

🧠 Quick Tricks

• Loops → add/multiply iterations

• Divide & Conquer → recurrence + Master Theorem

• Space → variables + structures + recursion

• Ignore constants & smaller terms

---

Shiksha: “Now I understand — we use complexity analysis, not runtime, to judge algorithms.”

Deepak: “And the ‘best’ algorithm depends on balancing time and space.”

Sagar: “Exactly! There’s no single best — it always depends on the problem.”

This article explores the importance of time and space complexity in evaluating algorithms, rather than relying on runtime due to its dependency on external factors. It breaks down the methods for calculating time complexity, including counting operations, loop analysis, and solving recurrences. Similarly, it explains space complexity through variables, data structures, recursion stack, and dynamic programming. Examples, such as linear and binary search, illustrate these concepts, while a comparison table highlights the differences in complexities. The article emphasizes that the "best" algorithm depends on balancing time and space for the given problem.

---