Space Complexity क्या है

Space complexity इस बारे में है कि काम करते समय आपको कितनी extra desk room चाहिए। कुछ tricks एक छोटे corner में fit होती हैं, जबकि कुछ को काम बड़ा होने पर फैलना पड़ता है।

In this page:

What is Space Complexity
Auxiliary Space
Space in Loops
Recursion and Space
Memory Choices

What is Space Complexity

Space complexity measure करता है कि एक algorithm को इसका input बढ़ने के साथ कितनी extra memory चाहिए, time complexity की तरह Big O उपयोग करके express किया गया। यह उतना ही मायने रखता है जितनी speed जब आप बड़े datasets या embedded devices जैसे memory-constrained environments के साथ काम कर रहे हों।

उदाहरण: What is Space Complexity

#include <iostream>
using namespace std;
int main() {
    int n = 5;
    int arr[5]; // extra memory grows with n: O(n) space
    for (int i = 0; i < n; i++) arr[i] = i * i;
    cout << "arr[4]: " << arr[4] << " (O(n) extra space)" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int n = 5;
        int[] arr = new int[n]; // extra memory grows with n: O(n) space
        for (int i = 0; i < n; i++) arr[i] = i * i;
        System.out.println("arr[4]: " + arr[4] + " (O(n) extra space)");
    }
}

n = 5
arr = [i * i for i in range(n)]  # extra memory grows with n: O(n) space
print("arr[4]:", arr[4], "(O(n) extra space)")

#include <stdio.h>
int main() {
    int n = 5;
    int arr[5]; /* O(n) extra space */
    for (int i = 0; i < n; i++) arr[i] = i * i;
    printf("arr[4]: %d (O(n) extra space)\n", arr[4]);
    return 0;
}

Auxiliary Space

Auxiliary space वह extra memory है जो एक algorithm input से आगे allocate करता है, जैसे एक temporary array, एक hash map, या recursion का call stack। दो algorithms जो दोनों O(n) time में चलते हैं auxiliary space में बहुत अलग हो सकते हैं, जो अक्सर उनके बीच असली deciding factor है।

उदाहरण: Auxiliary Space

#include <iostream>
using namespace std;
int main() {
    int input[] = {5, 3, 1, 4};
    int n = 4;
    int temp[4]; // auxiliary array beyond the input itself
    for (int i = 0; i < n; i++) temp[i] = input[i] * 2;
    cout << "temp[2]: " << temp[2] << " (auxiliary O(n) space)" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] input = {5, 3, 1, 4};
        int[] temp = new int[4]; // auxiliary array beyond the input itself
        for (int i = 0; i < 4; i++) temp[i] = input[i] * 2;
        System.out.println("temp[2]: " + temp[2] + " (auxiliary O(n) space)");
    }
}

input_arr = [5, 3, 1, 4]
temp = [x * 2 for x in input_arr]  # auxiliary list beyond the input itself
print("temp[2]:", temp[2], "(auxiliary O(n) space)")

#include <stdio.h>
int main() {
    int input[] = {5, 3, 1, 4};
    int temp[4]; /* auxiliary array beyond the input itself */
    for (int i = 0; i < 4; i++) temp[i] = input[i] * 2;
    printf("temp[2]: %d (auxiliary O(n) space)\n", temp[2]);
    return 0;
}

Space in Loops

एक loop जो बस एक running total, एक counter, या एक single swapped value track करता है O(1) constant space उपयोग करता है चाहे input कितना भी बड़ा हो, क्योंकि यह कभी n के अनुपात में नया storage allocate नहीं करता। यही कारण है कि in-place algorithms को जब memory tight हो तो सराहा जाता है।

उदाहरण: Space in Loops

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int total = 0; // just one variable: O(1) space, no matter arr size
    for (int i = 0; i < 5; i++) total += arr[i];
    cout << "Total: " << total << " (O(1) space)" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int total = 0; // O(1) space, no matter arr size
        for (int x : arr) total += x;
        System.out.println("Total: " + total + " (O(1) space)");
    }
}

arr = [1, 2, 3, 4, 5]
total = 0  # O(1) space, no matter list size
for x in arr:
    total += x
print("Total:", total, "(O(1) space)")

#include <stdio.h>
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int total = 0; /* O(1) space */
    for (int i = 0; i < 5; i++) total += arr[i];
    printf("Total: %d (O(1) space)\n", total);
    return 0;
}

Recursion and Space

हर recursive call अपने local variables याद रखने और कहां return करना है यह याद रखने के लिए call stack पर एक नया frame push करता है, इसलिए n levels गहराई तक जाने वाला एक recursion O(n) space उपयोग करता है भले ही यह कोई और allocation न करे। यह एक आम कारण है कि recursive solutions stack overflow errors पा सकते हैं जो उनके iterative equivalents नहीं पाते।

उदाहरण: Recursion and Space

#include <iostream>
using namespace std;
int sumTo(int n) {
    if (n == 0) return 0; // each call stays on the stack: O(n) space
    return n + sumTo(n - 1);
}
int main() {
    cout << "sumTo(5): " << sumTo(5) << " (O(n) stack space)" << endl;
    return 0;
}

public class Main {
    static int sumTo(int n) {
        if (n == 0) return 0; // O(n) stack space
        return n + sumTo(n - 1);
    }
    public static void main(String[] args) {
        System.out.println("sumTo(5): " + sumTo(5) + " (O(n) stack space)");
    }
}

def sum_to(n):
    if n == 0:
        return 0  # O(n) stack space
    return n + sum_to(n - 1)

print("sum_to(5):", sum_to(5), "(O(n) stack space)")

#include <stdio.h>
int sumTo(int n) {
    if (n == 0) return 0; /* O(n) stack space */
    return n + sumTo(n - 1);
}
int main() {
    printf("sumTo(5): %d (O(n) stack space)\n", sumTo(5));
    return 0;
}

Memory Choices

अच्छा algorithm design आमतौर पर time को space के लिए trade करना या इसका उल्टा है: results cache करना किसी algorithm को memory की कीमत पर तेज़ कर सकता है, जबकि एक in-place approach memory बचाता है लेकिन ज़्यादा careful, कभी-कभी धीमी, logic चाह सकता है। इस trade-off को पहचानना एक core DSA skill है।

उदाहरण: Memory Choices

#include <iostream>
using namespace std;
int main() {
    int arr[] = {5, 1, 4, 2};
    int n = 4;
    // In-place swap: saves memory (O(1) space), no extra array needed.
    for (int i = 0; i < n / 2; i++) {
        int tmp = arr[i];
        arr[i] = arr[n - 1 - i];
        arr[n - 1 - i] = tmp;
    }
    cout << "Reversed[0]: " << arr[0] << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 1, 4, 2};
        int n = 4;
        // In-place swap: O(1) space, no extra array needed.
        for (int i = 0; i < n / 2; i++) {
            int tmp = arr[i];
            arr[i] = arr[n - 1 - i];
            arr[n - 1 - i] = tmp;
        }
        System.out.println("Reversed[0]: " + arr[0]);
    }
}

arr = [5, 1, 4, 2]
arr.reverse()  # in-place: O(1) extra space, no new list built
print("Reversed[0]:", arr[0])

#include <stdio.h>
int main() {
    int arr[] = {5, 1, 4, 2};
    int n = 4;
    /* In-place swap: O(1) space, no extra array needed. */
    for (int i = 0; i < n / 2; i++) {
        int tmp = arr[i];
        arr[i] = arr[n - 1 - i];
        arr[n - 1 - i] = tmp;
    }
    printf("Reversed[0]: %d\n", arr[0]);
    return 0;
}

Chapter Quiz — Complete all 6 topics to unlock

0/6 topics done

Complete these topics first:

← Previous Lesson Time Complexity and Big O Notation Next Lesson → Best Worst and Average Case