Time Complexity and Space Complexity Analysis of Algorithms

Kisi bhi algorithm ko design karte waqt do critical parameters measure kiye jaate hain: Time Complexity (algorithm kitna time leta hai execute hone me) aur Space Complexity (algorithm ko run karne ke liye kitni memory ki zaroorat padti hai). Ek ideal algorithm dono resources ka optimal use karta hai.

1. Time Complexity Analysis

Time complexity actual seconds ya milliseconds me measure nahi ki ja sakti kyunki processor speed, architecture, aur background operating system processes har system par alag hote hain. Isliye, time complexity ko number of basic operations (such as comparisons, additions, memory assignments) ke terms me input size n ke function ke roop me measure kiya jata hai.

Types of Time Complexity:

• Worst-case Time Complexity [W(n)]: Maximum time jo algorithm kisi bhi input size n ke liye le sakta hai. Yeh upper bound guarantee karta hai.
• Best-case Time Complexity [B(n)]: Minimum time jo algorithm execute hone ke liye lega (e.g. Linear search me element pehli position par mil jaye toh O(1)).
• Average-case Time Complexity [A(n)]: Expected time over all possible valid inputs. Yeh calculation probability distribution par based hoti hai.

How to Calculate Time Complexity of Loops

Loops ki time complexity determine karne ke standard rules:

Case 1: Simple Linear Loop

// Loop runs exactly n times
for (int i = 0; i < n; i++) {
    // Constant time operations O(1)
    x = x + 1;
}
// Total Time Complexity = O(n)

Case 2: Nested Loops

// Outer loop runs n times, inner loop runs n times
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        c[i][j] = a[i][j] + b[i][j]; // O(1)
    }
}
// Total Time Complexity = n * n * O(1) = O(n^2)

Case 3: Logarithmic Loop (Multiplication/Division)

// Counter multiplies by 2 in each iteration
for (int i = 1; i <= n; i = i * 2) {
    // Executes: 1, 2, 4, 8, ..., 2^k <= n
    // k = log2(n)
}
// Total Time Complexity = O(log n)

2. Space Complexity Analysis

Space complexity ka matlab hota hai total memory amount jo algorithm ko execution ke dauran required hoti hai. Space complexity do parts se milkar banti hai:

Total Space = Fixed Space + Variable (Dynamic) Space

• Fixed Part: Instruction space (code bytes), simple variables (int, float), aur constants. Yeh input size par depend nahi karta.
• Variable Part: Dynamically allocated memory (malloc/calloc), reference variables, recursion stack space, aur input size n ke proportional arrays.

Auxiliary Space vs Space Complexity

Yeh distinction viva aur competitive exams me frequently pucha jata hai:

• Auxiliary Space: Algorithm dwara use kiya gaya extra ya temporary space, input data ko chhod kar. E.g., Merge sort me O(n) auxiliary array lagti hai.
• Space Complexity: Input data space + Auxiliary space ka sum.

+---------------------------+-----------------------------------+
| Algorithm / Operation     | Time Complexity | Space Auxiliary |
+---------------------------+-----------------------------------+
| Linear Search             | O(n)            | O(1)            |
| Binary Search (Iterative) | O(log n)        | O(1)            |
| Binary Search (Recursive) | O(log n)        | O(log n) stack  |
| Bubble / Selection Sort   | O(n^2)          | O(1)            |
| Merge Sort                | O(n log n)      | O(n)            |
| Quick Sort (Average)      | O(n log n)      | O(log n) stack  |
+---------------------------+-----------------------------------+

Agli post me hum start karenge Linear Data Structures me 1D Arrays: Memory Representation and Address Calculation.