# Big O Flashcards

What caes exist for time complexity

Best Case, Worse Case, Expected Case

Best Case

A complexity scenario that tells you the most favorable outcome. Often not very useful.

Worst Case

A complexity scenario that gives the least favorable outcome. Sometimes it is the same as the most likely outcome.

Expected Case

A complexity scenario that gives the most likely outcome. It is often equal to the least favorable outcome.

Constants should be dropped in big O notation (true/false)

True

Name the common big O notations in order of their rate of increase.

X! 2**X X**2 X log X X log X

ArrayList

Dynamically resized array. When array is at capacity, a new array with twice the capacity is created and all values are copied from the old array.

Amortized Time

When worst case happens every once in awhile and once it does happen, it won’t happen again for a long time.

Amortized Time of ArrayList

The total time complexity is o (x) with o (1) for each adding.

O (log N)

If we want to know how many times N elements can be halved, we instead ask the opposite question; how many times must we double a single element to get N elements? The answer is k times or 2**k = N or log (N)

Covert bases of logs

Log 10 (x) = Log 2 (x) / Log 2 (10). The only difference between logs of different bases is a constant factor.

Recursive Runtimes

Create a recursive tree and count the total number of nodes. Many times it is O (branches**depth). The space complexity is the depth of the tree.

Summing powers of 2

2^0 + 2^1+ 2^2 + … 2^(N-1) = 2**N - 1