Big O

Question 1

What caes exist for time complexity

Answer 1

Best Case, Worse Case, Expected Case

Question 2

Best Case

Answer 2

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

Question 3

Worst Case

Answer 3

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

Question 4

Expected Case

Answer 4

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

Question 5

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

Answer 5

True

Question 6

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

Answer 6

X! 2X X2 X log X X log X

Question 7

ArrayList

Answer 7

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.

Question 8

Amortized Time

Answer 8

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

Question 9

Amortized Time of ArrayList

Answer 9

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

Question 10

O (log N)

Answer 10

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)

Question 11

Covert bases of logs

Answer 11

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

Question 12

Recursive Runtimes

Answer 12

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.

Question 13

Summing powers of 2

Answer 13

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