If you're reading about complexity, you may come across some terminology like "Big Oh" notation and "asymptotic complexity", where an algorithm that takes about steps is referred to as .
We won't get into these in this chapter, but here's a little information in case you come across the terms in other reading.
"Big Oh" notation is a precise way to talk about complexity, and is used with "asymptotic complexity", which simply means how an algorithm performs for large values of *n*.
The "asymptotic" part means as *n* gets really large — when this happens, you are less worried about small details of the running time.
If an algorithm is going to take seven days to complete, it's not that interesting to find out that it's actually 7 days, 1 hour, 3 minutes and 4.33 seconds, and it's not worth wasting time to work it out precisely.

We won't use precise notation for asymptotic complexity (which says which parts of speed calculations you can safely ignore), but we will make rough estimates of the number of operations that an algorithm will go through. There's no need to get too hung up on precision since computer scientists are comfortable with a simple characterisation that gives a ballpark indication of speed.

For example, consider using selection sort to put a list of *n* values into increasing order.
(This is explained in the chapter on algorithms).
Suppose someone tells you that it takes 30 seconds to sort a thousand items.
Does that sounds like a good algorithm?
For a start, you'd probably want to know what sort of computer it was running on - if it's a supercomputer then that's not so good; if it's a tiny low-power device like a smartphone then maybe it's ok.

Also, a single data point doesn't tell you how well the system will work with larger problems. If the selection sort algorithm above was given 10 thousand items to sort, it would probably take about 50 minutes (3000 seconds) — that's 100 times as long to process 10 times as much input.

These data points for a particular computer are useful for getting an idea of the performance (that is, complexity) of the algorithm, but they don't give a clear picture.
It turns out that we can work out exactly how many steps the selection sort algorithm will take for *n* items: it will require about operations, or in expanded form, operations.
This formula applies regardless of the kind of computer it's running on, and while it doesn't tell us the time that will be taken, it can help us to work out if it's going to be reasonable.

From the above formula we can see why it gets bad for large values of *n* : the number of steps taken increases with the square of the size of the input.
Putting in a value of 1 thousand for *n* tells us that it will use 1,000,000/2 - 1,000/2 steps, which is 499,500 steps.

Notice that the second part (1000/2) makes little difference to the calculation. If we just use the part of the formula, the estimate will be out by 0.1%, and quite frankly, the user won't notice if it takes 20 seconds or 19.98 seconds. That's the point of asymptotic complexity — we only need to focus on the most significant part of the formula, which contains .

Also, since measuring the number of steps is independent of the computer it will run on, it doesn't really matter if it's described as or . The amount of time it takes will be proportional to both of these formulas, so we might as well simplify it to . This is only a rough characterisation of the selection sort algorithm, but it tells us a lot about it, and this level of accuracy is widely used to quickly but fairly accurately characterise the complexity of an algorithm. In this chapter we'll be using similar crude characterisations because they are usually enough to know if an algorithm is likely to finish in a reasonable time or not.