Time Complexity और Big O Notation

Big O यह describe करने जैसा है कि ज़्यादा काम होने पर कोई chore कितना ज़्यादा समय लेता है। दस dishes थोड़ा समय लेती हैं, लेकिन हज़ार dishes कहीं ज़्यादा समय लेती हैं, और Big O बताता है यह कितनी तेज़ी से बढ़ता है।

In this page:

What is Time Complexity
Big O Notation
Common Complexities
Counting Operations
Why Complexity Matters

What is Time Complexity

Time complexity यह describe करने का एक तरीका है कि किसी algorithm का running time इसके input size बढ़ने के साथ कैसे बढ़ता है, इसे चलाने वाली machine की specific speed पर निर्भर हुए बिना। यह practical सवाल का जवाब देता है: अगर मैं अपना input double करूं, क्या मेरा program लगभग उतना ही समय लेगा, दोगुना, या नाटकीय रूप से ज़्यादा?

उदाहरण: What is Time Complexity

#include <iostream>
using namespace std;
int main() {
    int n = 4;
    int steps = 0;
    for (int i = 0; i < n; i++) steps++;
    cout << "n=" << n << " steps=" << steps << endl;
    n = 8;
    steps = 0;
    for (int i = 0; i < n; i++) steps++;
    cout << "n=" << n << " steps=" << steps << " (grows with n)" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int n = 4, steps = 0;
        for (int i = 0; i < n; i++) steps++;
        System.out.println("n=" + n + " steps=" + steps);
        n = 8; steps = 0;
        for (int i = 0; i < n; i++) steps++;
        System.out.println("n=" + n + " steps=" + steps + " (grows with n)");
    }
}

for n in (4, 8):
    steps = 0
    for i in range(n):
        steps += 1
    print(f"n={n} steps={steps}")

#include <stdio.h>
int main() {
    int n = 4, steps = 0;
    for (int i = 0; i < n; i++) steps++;
    printf("n=%d steps=%d\n", n, steps);
    n = 8; steps = 0;
    for (int i = 0; i < n; i++) steps++;
    printf("n=%d steps=%d (grows with n)\n", n, steps);
    return 0;
}

Big O Notation

Big O notation input size n उपयोग करके उस growth की एक upper bound देता है, constant factors और lower-order terms को नज़रअंदाज़ करते हुए क्योंकि n बड़ा होने पर वे कम से कम मायने रखते हैं। किसी algorithm को O(n) या O(n log n) लिखना आपको बहुत अलग code pieces को समान footing पर compare करने देता है।

उदाहरण: Big O Notation

#include <iostream>
using namespace std;
// O(n): time grows linearly with input size, ignoring constants.
int sumArray(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) total += arr[i];
    return total;
}
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    cout << "O(n) sum: " << sumArray(arr, 5) << endl;
    return 0;
}

public class Main {
    // O(n): time grows linearly with input size, ignoring constants.
    static int sumArray(int[] arr) {
        int total = 0;
        for (int x : arr) total += x;
        return total;
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println("O(n) sum: " + sumArray(arr));
    }
}

# O(n): time grows linearly with input size, ignoring constants.
def sum_array(arr):
    total = 0
    for x in arr:
        total += x
    return total

print("O(n) sum:", sum_array([1, 2, 3, 4, 5]))

#include <stdio.h>
/* O(n): time grows linearly with input size, ignoring constants. */
int sumArray(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) total += arr[i];
    return total;
}
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    printf("O(n) sum: %d\n", sumArray(arr, 5));
    return 0;
}

Common Complexities

O(1) constant time input size के साथ नहीं बदलता, जैसे array indexing। O(log n) logarithmic time, जैसे binary search, बहुत बड़े inputs के लिए भी मुश्किल से बढ़ता है।

O(n) linear time हर चीज़ को एक बार scan करता है, और O(n²) quadratic time, naive nested loops में आम, n के हज़ारों तक बढ़ने पर painfully धीमा हो जाता है।

उदाहरण: Common Complexities

#include <iostream>
using namespace std;
int main() {
    int arr[] = {10, 20, 30, 40};
    cout << "O(1) access arr[2]: " << arr[2] << endl;
    int sum = 0;
    for (int i = 0; i < 4; i++) sum += arr[i]; // O(n)
    cout << "O(n) sum: " << sum << endl;
    int pairs = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            pairs++; // O(n^2)
    cout << "O(n^2) pairs counted: " << pairs << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40};
        System.out.println("O(1) access arr[2]: " + arr[2]);
        int sum = 0;
        for (int i = 0; i < 4; i++) sum += arr[i];
        System.out.println("O(n) sum: " + sum);
        int pairs = 0;
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                pairs++;
        System.out.println("O(n^2) pairs counted: " + pairs);
    }
}

arr = [10, 20, 30, 40]
print("O(1) access arr[2]:", arr[2])
total = sum(arr)  # O(n)
print("O(n) sum:", total)
pairs = sum(1 for i in range(4) for j in range(4))  # O(n^2)
print("O(n^2) pairs counted:", pairs)

#include <stdio.h>
int main() {
    int arr[] = {10, 20, 30, 40};
    printf("O(1) access arr[2]: %d\n", arr[2]);
    int sum = 0;
    for (int i = 0; i < 4; i++) sum += arr[i];
    printf("O(n) sum: %d\n", sum);
    int pairs = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            pairs++;
    printf("O(n^2) pairs counted: %d\n", pairs);
    return 0;
}

Counting Operations

Formal proofs के बिना complexity estimate करने का एक practical तरीका यह count करना है कि algorithm का main operation (एक comparison, एक addition, एक loop iteration) n के सापेक्ष कितनी बार चलता है। उसी input size पर nested loops O(n²) या बदतर होने का एक strong signal हैं।

उदाहरण: Counting Operations

#include <iostream>
using namespace std;
int main() {
    int n = 4;
    int comparisons = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            comparisons++;
    cout << "n=" << n << " nested-loop comparisons=" << comparisons << " (n^2)" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int n = 4, comparisons = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                comparisons++;
        System.out.println("n=" + n + " nested-loop comparisons=" + comparisons + " (n^2)");
    }
}

n = 4
comparisons = sum(1 for i in range(n) for j in range(n))
print(f"n={n} nested-loop comparisons={comparisons} (n^2)")

#include <stdio.h>
int main() {
    int n = 4, comparisons = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            comparisons++;
    printf("n=%d nested-loop comparisons=%d (n^2)\n", n, comparisons);
    return 0;
}

Why Complexity Matters

Complexity analysis मायने रखता है क्योंकि यह उन inputs पर behavior predict करता है जिन्हें आपने अभी तक test नहीं किया। दो algorithms जो दोनों एक 10-element test case पर सही काम करते हैं एक million-element production dataset पर पूरी तरह अलग behave कर सकते हैं, और Big O वह है जो बताता है कौन सा टिकेगा।

उदाहरण: Why Complexity Matters

#include <iostream>
using namespace std;
long linearSteps(int n) { return n; }
long quadraticSteps(int n) { return (long)n * n; }
int main() {
    int n = 1000000;
    cout << "O(n) steps: " << linearSteps(n) << endl;
    cout << "O(n^2) steps: " << quadraticSteps(n) << " (much worse at scale)" << endl;
    return 0;
}

public class Main {
    static long linearSteps(int n) { return n; }
    static long quadraticSteps(int n) { return (long) n * n; }
    public static void main(String[] args) {
        int n = 1000000;
        System.out.println("O(n) steps: " + linearSteps(n));
        System.out.println("O(n^2) steps: " + quadraticSteps(n) + " (much worse at scale)");
    }
}

def linear_steps(n):
    return n

def quadratic_steps(n):
    return n * n

n = 1000000
print("O(n) steps:", linear_steps(n))
print("O(n^2) steps:", quadratic_steps(n), "(much worse at scale)")

#include <stdio.h>
long linearSteps(int n) { return n; }
long quadraticSteps(int n) { return (long)n * n; }
int main() {
    int n = 1000000;
    printf("O(n) steps: %ld\n", linearSteps(n));
    printf("O(n^2) steps: %ld (much worse at scale)\n", quadraticSteps(n));
    return 0;
}

Chapter Quiz — Complete all 6 topics to unlock

0/6 topics done

Complete these topics first:

← Previous Lesson What is DSA Next Lesson → Space Complexity