How does Big O relate to N+1?

Question

Big 0 attempts to answer the question of inefficiency in algorithmic complexity. N+1 describes inefficiency as it relates to database queries in terms of separate queries to populate each item in a collection.

I'm currently trying to get my head around each of these concepts in different contexts at work, and I'm wondering now if somebody could explain whether these two concepts relate to each other in any way? Could somebody provide a description that would apply to both of them?

Answer 1

Big O notation for complexity is defined using number of operations of a Turing machine and can therefore describe any algorithm. The N+1 select problem describes inefficient relational algorithm (query), which needs always N+1 operations for every record. As that query is an algorithm, you can analyse its complexity.

O(N+1)=O(N)

This means you have linear complexity. Now if we used the correct algorithm, we would need only one operation (select) per record for each of two tables. The complexity would be:

O(2)=O(1)

This algorithm has constant complexity. This shows, that by analysing the complexity of both algorithms you would see which one suffers from the N+1 selects problem.

Is this clear?