Linear time v.s. Quadratic time

Question

Often, some of the answers mention that a given solution is linear, or that another one is quadratic.

How to make the difference / identify what is what?

Can someone explain this, the easiest possible way, for the ones like me who still don't know?

Answer 1

A method is linear when the time it takes increases linearly with the number of elements involved. For example, a for loop which prints the elements of an array is roughly linear:

for x in range(10):
    print x

because if we print range(100) instead of range(10), the time it will take to run it is 10 times longer. You will see very often that written as O(N), meaning that the time or computational effort to run the algorithm is proportional to N.

Now, let's say we want to print the elements of two for loops:

for x in range(10):
    for y in range(10):
        print x, y

For every x, I go 10 times looping y. For this reason, the whole thing goes through 10x10=100 prints (you can see them just by running the code). If instead of using 10, I use 100, now the method will do 100x100=10000. In other words, the method goes as O(N*N) or O(N²), because every time you increase the number of elements, the computation effort or time will increase as the square of the number of points.