Big O

Question 1

What is Big O?

Answer 1

Big 0 time is the language and metric we use to describe the efficiency of algorithms.

Question 2

What is Time Complexity?

Answer 2

The upper time that an algorithm can take to finish

Question 3

What is Space Complexity?

Answer 3

The upper space that an algorithm can take to finish

Question 4

When should I add the runtimes?

Answer 4

If your algorithm is in the form “do this, then, when you’re all done, do that” then you add the runtimes.

Question 5

When should I multiply the runtimes?

Answer 5

If your algorithm is in the form “do this for each time you do that” then you multiply the runtimes.

Question 6

What is Amortized Time?

Answer 6

When the array hits the capacity, the ArrayList will create a new one with double the capacity. It allows us to describe that, yes, this worst case happens every once in a while. But once it happens, it won’t happen again for so long that the cost is “amortized.”

Question 7

Log N Runtimes

Answer 7

When you see a problem where the number of elements in the problem space gets halved each time, that will likely be a 0(log N) runtime.

Question 8

Recursive Runtimes

Answer 8

When you have a recursive function that makes multiple calls, the runtime will often (but not always) take like O(branches ^ (N+1)), where branches are the number of times each recursive call branches. In this case, this gives us 0( 2”).