Database design best practices in SQL - Time & Space Complexity

Time Complexity: Database design best practices

O(log n)

Understanding Time Complexity

When designing a database, it is important to understand how the structure affects the speed of queries.

We want to know how the design choices impact the time it takes to get data as the database grows.

Scenario Under Consideration

Analyze the time complexity of this simple query on a well-designed table.

SELECT customer_name, order_date
FROM orders
WHERE customer_id = 12345;

This query fetches orders for one customer using an indexed column.

Identify Repeating Operations

Look for repeated steps in the query process.

• Primary operation: Searching the index for matching customer_id.
• How many times: Depends on the number of matching orders for that customer.

How Execution Grows With Input

As the total number of orders grows, the index helps keep search fast.

Input Size (n)	Approx. Operations
10	About 3-4 steps to find data
100	About 5-7 steps
1000	About 7-10 steps

Pattern observation: The search steps grow slowly even if the data grows a lot, thanks to indexing.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find data grows slowly as the database gets bigger, making queries efficient.

Common Mistake

[X] Wrong: "Adding more data always makes queries take much longer."

[OK] Correct: Proper design with indexes keeps search time growing slowly, not linearly.

Interview Connect

Understanding how design affects query speed shows you know how to build databases that work well as they grow.

Self-Check

"What if we removed the index on customer_id? How would the time complexity change?"