1. What is DSA & Why It Matters

What is DSA?

Data Structures are ways of organising data in memory so it can be accessed and modified efficiently. Algorithms are step-by-step procedures for solving problems using that data.

Think of it this way:

• A data structure is like a container — a filing cabinet, a shopping cart, a to-do list.
• An algorithm is like a procedure — how you sort those files, search your cart, or prioritise tasks.

Choosing the right container and procedure for the job is what separates fast software from slow software.

---

Why Does a Software Engineer Need DSA?

Scenario	Without DSA	With DSA
Search 1M user records	Loop through all 1M → slow	Hash map lookup → instant
Auto-complete as you type	Re-scan all words each keypress	Trie lookup → fast
Undo/redo in a text editor	Re-compute full history	Stack → trivial
Find shortest delivery route	Try every path → impossible	Dijkstra's algorithm
Sort a leaderboard of 10M scores	Random order → unusable	Merge sort → done in seconds

---

Big-O Notation — The Language of Efficiency

Big-O tells you how the runtime grows as the input size $n$ grows. It's not about exact milliseconds — it's about the shape of the growth curve.

O(1)       → Constant    — doesn't matter how big n is; always the same speed
O(log n)   → Logarithmic — doubles input, adds one more step (e.g. binary search)
O(n)       → Linear      — doubles input, doubles time (e.g. single loop)
O(n log n) → Linearithmic — sorting algorithms
O(n²)      → Quadratic   — doubles input, 4x the time (e.g. nested loop)
O(2^n)     → Exponential — each extra element doubles the work (e.g. brute force subsets)

Practical rule of thumb: If your input can be 1,000,000 items, an $O(n^2)$ algorithm will be too slow. Aim for $O(n)$ or $O(n \log n)$.

# O(1) — constant time
def get_first(items: list) -> object:
    return items[0]   # doesn't matter if list has 10 or 10 million items

# O(n) — linear time
def find_max(items: list[int]) -> int:
    maximum = items[0]
    for x in items:          # one pass through all n items
        if x > maximum:
            maximum = x
    return maximum

# O(n²) — quadratic time — AVOID for large inputs
def has_duplicate_slow(items: list) -> bool:
    for i in range(len(items)):
        for j in range(i + 1, len(items)):   # nested loop = n² comparisons
            if items[i] == items[j]:
                return True
    return False

# O(n) alternative — using a set
def has_duplicate_fast(items: list) -> bool:
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

Space Complexity

Beyond runtime, always consider how much memory your solution uses. An algorithm that's fast but uses 10GB of RAM for a 1MB input is not useful in production.

O(1) space  → uses a fixed amount of extra memory regardless of input size
O(n) space  → uses memory proportional to input size (e.g. storing a copy of the input)

---