 <p>If you look at Pascal's triangle as a matrix, and you want to find the complexity of building that matrix up to size <code>n x k</code>, then the big-oh of that will be <code>O(n*k)</code>. Obviously you can't get better than that, because that's the size of the matrix.</p> <p>How do we get that? Use the following simplified recurrence for combinations:</p> <pre><code>C(n, k) = C(n - 1, k) + C(n - 1, k - 1) </code></pre> <p>Computing just a single combination has the same complexity (if using memoization).</p>