Time Complexity

What you are watching

A loop nested inside another loop, running over eight elements, with both of its costs counted as they happen. Down the left, one tile appears for each turn of the outer loop, giving eight visits in total. On the right, aligned with those tiles row for row, one square fills for each turn of the inner loop, and because the inner loop runs all the way across for every single step of the outer one, the block ends up eight squares by eight squares. The same four lines of code produce a column of n and a block of n times n, which is the difference between linear and quadratic time.