….

Foundations

Understanding time and space complexity is the backbone of mastering Data Structures and Algorithms (DSA). Before diving into advanced problem-solving, you need to know how to measure the efficiency of an algorithm and compare different approaches. This is where Big-O notation and algorithm analysis come in.

---

⏱ Time Complexity (How fast is your algorithm?)

Time complexity describes how the execution time of an algorithm grows with the size of the input (n). Instead of measuring in seconds (which depends on your hardware), we use mathematical notation to express growth.

• O(1) – Constant Time: The algorithm takes the same time regardless of input size.
  Example: Accessing an element in an array.
• O(log n) – Logarithmic Time: The runtime grows slowly as input size increases.
  Example: Binary Search.
• O(n) – Linear Time: The runtime grows directly with the input size.
  Example: Traversing a list.
• O(n log n) – Linearithmic Time: Slightly more than linear, common in efficient sorting algorithms.
  Example: Merge Sort, Quick Sort (average case).
• O(n²), O(n³)… – Polynomial Time: Runtime grows rapidly with input size.
  Example: Nested loops, brute force solutions.
• O(2ⁿ), O(n!) – Exponential/Factorial Time: Extremely inefficient, only feasible for very small inputs.
  Example: Solving the Traveling Salesman Problem via brute force.

👉 Rule of thumb: Always aim for the lowest possible time complexity.

---

💾 Space Complexity (How much memory does your algorithm use?)

Space complexity measures the amount of memory an algorithm needs during execution. This includes:

1. Fixed Part: Memory required for constants, variables, and program instructions.
2. Variable Part: Memory that changes with input size, such as dynamic arrays, recursion stacks, and auxiliary data structures.

Examples:

• A simple loop with no extra data → O(1) space.
• Using recursion with depth n → O(n) space.
• Creating an auxiliary array → depends on its size.

👉 Balance is key: Sometimes, you trade space for time (e.g., using hash maps to achieve O(1) lookups).

---

🔍 How to Analyze Algorithms

When analyzing an algorithm, follow these steps:

1. Identify the input size (n): What determines the workload? (array length, number of nodes, etc.)
2. Count the operations: Look for loops, recursive calls, and key operations that scale with input size.
3. Express in Big-O notation: Keep only the most significant term, drop constants.
   • Example: 3n² + 2n + 5 → O(n²)
4. Consider best, average, and worst cases: Some algorithms behave differently depending on the input.
   • Example: Quick Sort is O(n log n) on average but O(n²) in the worst case.
5. Evaluate space usage: Does it use recursion, temporary arrays, or hash tables?

---

⚡ Why It Matters

• Optimization: Efficient algorithms save time and resources.
• Scalability: Real-world applications often deal with millions of data points—efficiency is not optional.
• Interview Prep: Big-O is one of the most common topics in coding interviews.

---