DSA Series Chapter 1 Time & Space Complexity ( C Edition)

on

 

[Follow here] for daily coding insights.

 Time & Space Complexity 

 C Edition (Beginner → Pro, Interview-Ready)

    Understanding complexity is language-agnostic, but C brings low-level details (manual memory, pointers, stack/heap) that make space complexity especially important. This post covers intuition, Big-O notation, C examples, and interview-style questions.

 1. What is Time Complexity?

    Time complexity measures how the running time grows with input size n. In C we still count operations (loops, comparisons, recursive calls) rather than wall-clock time.

 2. Why Complexity Matters (C perspective)

  • C programs are used in system-level and performance-critical code — inefficient algorithms can be catastrophic.

  • Manual memory management (malloc/free) makes space-efficient algorithms crucial.

 3. Big-O, Θ, Ω — quick recap

  • O(f(n)) — worst-case upper bound

  • Θ(f(n)) — tight/average-case bound

  • Ω(f(n)) — best-case lower bound

Interviewers mostly ask Big-O (worst-case).

 4. Standard Complexities to Memorize

O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!)

 5. C Examples — Simple, clear

Constant time — O(1)

int get_first(int arr[], int n) {
    if (n == 0) return -1;
    return arr[0]; // O(1)
}

Linear time — O(n)

int sum_array(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; ++i) { // loop runs n times
        sum += arr[i];
    }
    return sum; // O(n)
}

Quadratic time — O(n^2)

void print_pairs(int arr[], int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            printf("%d %d\n", arr[i], arr[j]);
        }
    }
} // O(n^2)

Logarithmic time — O(log n) (iterative binary search)

int binary_search(int arr[], int n, int key) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) { // halves search space each iteration
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == key) return mid;
        else if (arr[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1; // O(log n)
}

Divide & Conquer — O(n log n) (merge sort outline)

// Merge and merge_sort prototypes (full implementation available on request)
void merge_sort(int arr[], int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    merge_sort(arr, l, m);
    merge_sort(arr, m+1, r);
    merge(arr, l, m, r); // merging is O(n) per level -> total O(n log n)
}

 6. Space Complexity in C — key points

  • Auxiliary space = extra memory your algorithm uses (excluding input).

  • In C, memory sources:

    • Stack: local variables, recursion frames. Limited. Recursion depth d uses O(d) stack space.

    • Heap: malloc/calloc memory. You control it and must free it.

  • Example: copying an array with malloc uses O(n) auxiliary space.

int *copy_array(int arr[], int n) {
    int *b = malloc(n * sizeof(int)); // O(n) extra space on heap
    for (int i = 0; i < n; ++i) b[i] = arr[i];
    return b;
}

 7. Common data-structure operation complexities (C-centric)

  • Array access arr[i] → O(1)

  • Insert at end (dynamic array amortized) → O(1) amortized (if implemented)

  • Insert at beginning (array) → O(n) (needs shifting)

  • Linked list insert at head → O(1)

  • Stack/Queue operations (array or linked list) → O(1)

  • Hash table average → O(1) (depends on load factor & chaining/rehashing)

  • Binary search tree (balanced) → O(log n) search/insert/delete, worst-case O(n) if unbalanced

 8. Recursion complexity (C)

Recursion in C consumes stack memory. Example:

void recurse(int n) {
    if (n == 0) return;
    recurse(n - 1); // time O(n), stack depth O(n)
}

Time: O(n) — one call per integer. Space: O(n) — recursion depth.

 9. Practical C pitfalls that affect complexity

  • Using strlen() inside a loop over a string: strlen() is O(n) — avoid repeating it in conditional checks.

  • Frequent malloc/free inside hot loops increases constant factors — algorithmic complexity may be same but runtime worsens.

  • Pointer arithmetic vs array indexing: both O(1), but pointer arithmetic is sometimes slightly faster in tight loops.

 10. Interview-style C Examples & Explanations

Q1: What is complexity of:

for (int i = 1; i <= n; i = i * 2) printf("%d\n", i);

Answer: O(log n) — loop runs ~log₂n times.

Q2: Complexity of:

for (int i = 0; i < n; ++i)
    for (int j = 0; j < i; ++j) printf(".");

Answer: O(n²) — sum of 0..n-1 = O(n²).

Q3: Recurrence:

void f(int n) {
    if (n <= 1) return;
    f(n/2);
    f(n/2);
}

Answer: T(n) = 2T(n/2) + O(1) → O(n).

 11. 20 Practice Questions (C-flavored)

  1. What is the complexity of accessing arr[i]?

  2. Complexity of iterating over an n-element array?

  3. Complexity of nested loop for(i=0;i<n;i++) for(j=0;j<n;j++)?

  4. Complexity of iterative binary search on a sorted array?

  5. Complexity of merge sort (time and extra space)?

  6. Complexity of quicksort average and worst-case?

  7. Complexity of inserting at head of singly linked list?

  8. Complexity of searching in an unsorted array?

  9. Time to compute strlen() on a C string of length n?

  10. Complexity of copying an array using memcpy()? (Consider it O(n))

  11. Space cost of recursive factorial implemented in C?

  12. Complexity of BFS on a graph with V vertices, E edges?

  13. Complexity of deleting middle node in singly linked list if you have pointer to it?

  14. Complexity of pushing and popping from stack implemented with array?

  15. Complexity of checking palindrome by comparing characters from both ends?

  16. Complexity of dynamic array doubling strategy amortized insert?

  17. Complexity of finding duplicates using nested loops vs using hash table?

  18. Complexity of building a heap from an array (heapify)? (O(n))

  19. Complexity of Dijkstra using binary heap? (O((V+E) log V))

  20. Space complexity of storing adjacency matrix vs adjacency list?


 12. Quick Tips for Writing Efficient C Code

  • Avoid repeated strlen() or other O(n) calls inside loops. Cache results.

  • Minimize heap allocations in hot paths — reuse memory if possible.

  • Prefer iterative solutions if recursion depth may exceed stack limits.

  • Use -O2/-O3 compiler optimizations for contest builds (but rely on algorithmic complexity, not compiler alone).

  • Know standard library complexities (e.g., qsort() average O(n log n), memcpy() O(n)).

Conclusion

This C version mirrors the Python post but highlights memory management and low-level operations that matter in systems programming and contests. Master these concepts in C and Python — you’ll be prepared for both coding rounds and system-level interviews.

ALSO CHECK 

DS(Data Structure) Python Edition






Tail Recursion Optimization: How Compilers Convert Recursion Into Iteration


Advanced Recursion: Memoization vs. Tabulation — The Deep Optimization Blueprint for Professionals


Advanced Sorting Algorithms: Merge Sort Internals — Merge Tree, Cache Behavior & Real Cost Analysis


Enjoyed this post? [Follow here] for daily coding insights.

Comments

Post a Comment