First Normal Form (1NF) in SQL - Time & Space Complexity

Time Complexity: First Normal Form (1NF)

O(n)

Understanding Time Complexity

When we check if a database table follows First Normal Form, we look at how data is organized in rows and columns.

We want to understand how the work needed to verify this grows as the table gets bigger.

Scenario Under Consideration

Analyze the time complexity of this SQL query that checks for repeated groups in a table.

SELECT CustomerID, COUNT(OrderID) AS OrderCount
FROM Orders
GROUP BY CustomerID
HAVING COUNT(OrderID) > 1;
    

This query finds customers who have more than one order, helping to check if data is stored in separate rows as 1NF requires.

Identify Repeating Operations

Look at what repeats as the query runs:

• Primary operation: Scanning all rows in the Orders table.
• How many times: Once for each row, to count orders per customer.

How Execution Grows With Input

As the number of orders grows, the query must check each one to count them by customer.

Input Size (n)	Approx. Operations
10	About 10 row checks
100	About 100 row checks
1000	About 1000 row checks

Pattern observation: The work grows directly with the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to check 1NF grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "Checking 1NF takes the same time no matter how many rows there are."

[OK] Correct: The database must look at each row to find repeated groups, so more rows mean more work.

Interview Connect

Understanding how checking data rules like 1NF scales helps you explain database design clearly and shows you know how data size affects work.

Self-Check

"What if the table had an index on CustomerID? How would that change the time complexity of checking 1NF?"