Skip to content

Instantly share code, notes, and snippets.

@jrf0110
Last active August 29, 2015 14:15
Show Gist options
  • Save jrf0110/f2ad77d8423a3e06bc8a to your computer and use it in GitHub Desktop.
Save jrf0110/f2ad77d8423a3e06bc8a to your computer and use it in GitHub Desktop.

The Big(O) for IO-bound Operations

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment