Big(O) notation is great for describing computations on large data-sets in a synchronous programming environment, but what about IO-bound operations?
Big(IO)
Let n
represent the complexity of an asynchronous operation that takes a non-constant time t
to complete. Then an asynchronous operation that starts only after a previous operation (async) has been completed (serial asynchrony) is represented as n1 * n2
or simply n^2
. Two asynchronous operations started at the same time is represented as n1 + n2
or 2n
. Since we're waiting for both operations to complete, but they were fired off in near parallel, then we can consider the time t3
to be equal max( t1, t2 )
. Therefore, the Big(IO) of any kn
is to be considered equal.
An async series operation over an array of length n
should be Big(IO) = n^n
Since any "parallel" async operations can be considered to be equal to the constituent operation whose duration is the longest, we can just say any amount of parallel ops is simply equal to n
.
These are just ramblings, but it may be useful in describing an overview of performance for some things. Consider the route: GET /users/:id
. First, a request comes in, and we lookup the session for the request. That's n
. Only after session comes back can we lookup the user's permissions. That makes n^2
. Now, in "parallel", we read the user view from disk (n
) and also lookup the user record itself (2n
). All-in-all, that makes the BigIO for the request n^3
.