Data Structures and Algorithms in C (DSA)

📘 Time and Space Complexity

Time and Space Complexity are key tools for analyzing how efficient an algorithm is. Efficiency means how fast (time) and how much memory (space) an algorithm uses as the input size grows. Understanding this helps you write better, scalable code.

⏱️ Time Complexity (with Examples)

Time Complexity is used to estimate how long an algorithm takes to complete. It is measured as a function of input size n.

• O(1) — Constant Time: No matter the input size, the algorithm takes the same time.
  int x = arr[0]; → Accessing an array element by index is always O(1).
• O(n) — Linear Time: Time grows proportionally with input.
  for (int i = 0; i < n; i++) { sum += arr[i]; }
• O(log n) — Logarithmic Time: Reduces input size in each step.
  Binary Search on sorted array takes O(log n).
• O(n log n): Typical for efficient sorting algorithms like Merge Sort or Quick Sort (average case).
• O(n²) — Quadratic Time: Time grows with square of input size.
  for (i=0; i<n; i++) for (j=0; j<n; j++) → Nested loops
• O(2ⁿ) — Exponential Time: Growth doubles with each new input. Very slow.
  Fibonacci using Recursion: fib(n) = fib(n-1) + fib(n-2)

💾 Space Complexity (with Examples)

Space Complexity is the total memory space used by the algorithm including input, temporary variables, call stack, etc.

• O(1): No extra space used.
  Swapping two variables using temp: int temp = a; a = b; b = temp;
• O(n): Storing n elements.
  int* copy = malloc(n * sizeof(int));
• O(n²): Creating a 2D array or matrix.
  int matrix[100][100]; for a graph adjacency matrix.

🔍 Big O vs Θ vs Ω

Big O (O): Describes the worst-case time/space an algorithm will take.

Big Omega (Ω): Describes the best-case performance.

Big Theta (Θ): Represents the average-case or tight bound.

✅ Summary

• Time complexity tells how long your algorithm runs.
• Space complexity tells how much memory it uses.
• Use Big O for interview prep and real-world scalability.
• Avoid unnecessary memory and nested loops where possible.

📤 Coming Next

Up next: Recursion and Stack Memory — how functions call themselves and how memory is handled behind the scenes.