The complexity of an algorithm is a measure of the amount of work required to complete the algorithm in the worst case scenario. When we are looking at networks, the worst case is generally given by a complete network. Remember that a complete network has every node directly connected to every other node in the network.

The degree of complexity of an algorithm tells you how much extra work would need to be done if the problem were to be increased in size.

Constant complexity, O(1), means that the amount of work is constant, and is independent of the size of the problem.

Linear complexity, O(n), means that if the problem doubles in size, there will be double the work to do.

Quadratic complexity, O(n^2), indicates that there will be four times the amount of work if the size of the problem is doubled.

Exponential, logarithmic and many other degrees of complexity are possible based on the size and runtime of the algorithm.