Big O measures how a program's work increases as you give it more data. It helps us see if code will stay fast as it handles more items.

Growth Rate Basics

This means a task takes the same amount of effort regardless of data size. An example is looking up a single item if you already know exactly where it is.

Constant Time O(1)

The work grows at a steady pace, directly matching the amount of data. If you have ten times more items, the program takes ten times longer to finish.

Linear Time O(n)

This is very fast because the task gets easier by cutting the remaining work in half at every step. It is similar to finding a name in a phone book.

Logarithmic Time O(log n)

The work grows very quickly because you are doing a task for every item, inside another task. This often happens when you compare every item to every other item.

Quadratic Time O(n^2)

Big O usually looks at the absolute slowest a program could run. This prepares us for the worst scenario so we are not surprised by slow performance later.

The Worst Case

This measures the amount of memory or storage a program uses while running. Some programs are fast but need a lot of room to keep track of information.

Space Complexity

In Big O, we ignore small numbers to focus on the big picture. We care more about how the work scales than the exact number of steps taken.

Dropping the Constants

The work doubles with every single new piece of data added. This is very slow and becomes impossible for computers to finish quite quickly.

Exponential Growth O(2^n)

This is the slowest speed, often found when checking every possible way to arrange a set of items. It is only used for very specific, complex problems.

Factorial Growth O(n!)

Scalability is how well a program handles massive amounts of information. Big O tells us if a program can handle huge datasets without crashing.

The Phone Book Trick