O(1) Order

• Retrieving any single row from a table

  SELECT TOP 1 * FROM table;

O(log N) Order

• Filtering with a WHERE clause on an indexed column

Because this is O(log N), the time complexity does not increase much even as the table size grows.

O(N) Order

In the following cases, time complexity increases linearly with the number of rows:

• SELECT all rows
• Filtering with a WHERE clause ※ O(N) when there is no index
• Counting rows in a table with count(*)

O(N log N) Order

• Sorting with an ORDER BY clause

O(N²) Order

In the following cases, time complexity increases polynomially with the number of rows (increases drastically).

• Table joins
  • Because each row in table A is joined with each row in table B

However, depending on the join algorithm, the complexity may be as follows:

• Hash join
  • O(M+N)
• Merge join
  • O(M+N)
  • O(M log M + N log N)
  • O(M + N log N)
• Nested loop join
  • O(N²)

References

How To Write Better SQL Queries: The Definitive Guide – Part 2

Understanding Algorithmic Time Efficiency in SQL Queries

Big-O Cheat Sheet