How well a solution to some problem will work when the size of
the problem increases.
For example, a central
server of some kind with ten
clients may perform adequately but with a thousand clients
it might fail to meet response time requirements. In this
case, the average response time probably scales linearly with
the number of clients, we say it has a
complexity of O(N)
("order N") but there are problems with other complexities.
E.g. if we want N nodes in a network to be able to communicate
with each other, we could connect each one to a central
exchange, requiring O(N) wires or we could provide a direct
connection between each pair, requiring O(N^2) wires (the
exact number or formula is not usually so important as the
highest power of N involved).
(1995-03-29)