# Big O Flashcards

1
Q

What caes exist for time complexity

A

Best Case, Worse Case, Expected Case

2
Q

Best Case

A

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

3
Q

Worst Case

A

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

4
Q

Expected Case

A

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

5
Q

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

A

True

6
Q

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

A

X! 2X X2 X log X X log X

7
Q

ArrayList

A

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.

8
Q

Amortized Time

A

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

9
Q

Amortized Time of ArrayList

A

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

10
Q

O (log N)

A

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)

11
Q

Covert bases of logs

A

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

12
Q

Recursive Runtimes

A

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.

13
Q

Summing powers of 2

A

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