How does Big O relate to N + 1?

Question

Big 0 tries to answer the question about the inefficiency of algorithmic complexity. N + 1 describes inefficiency because it refers to database queries in terms of individual queries to populate each item in the collection.

I am currently trying to understand each of these concepts in different contexts at work, and now I wonder if anyone can explain whether these two concepts are related to each other? Can someone provide a description that will apply to both of them?

Answer 1

The Big O values ​​for complexity are determined using the number of operations of the Turing machine and therefore can describe any algorithm. The selection problem N + 1 describes an inefficient relational algorithm (query), which always requires the operation N + 1 for each record. Since this query is an algorithm, you can analyze its complexity.

O (N + 1) = O (N)

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

O (2) = O (1)

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

Is this clear?