Big O Notation

Question 1

Define Big O Notation

Answer 1

Metric used to measure how efficient an algorithm is. How an algorithm scales with input

Question 2

Expected Case

Answer 2

Usually the runtime that occurs on a daily basis

Question 3

Worst Case

Answer 3

The unlucky case, usually runs the worst or is least performant

Question 4

Best Case

Answer 4

The lucky case, usually runs the fastest

Question 5

Dropping non dominant term

Answer 5

Getting rid of all terms smaller than the largest big O value. Constants can also be dropped

Question 6

Space complexity

Answer 6

Big O can also be used to describe space complexity. This is usually to describe how much space is needed for a data structure IN the algorithm.

Question 7

What is the big O of two for loops that aren’t nested and iterate through the same array length n?

Answer 7

2n, but you can drop the terms. This would run in linear time or O(n)

Question 8

What is the big O of two for loops that are nested and iterate through the same array length n?

Answer 8

Since for each value of the first loop has to wait for a whole iteration of the second, the loop would run in O(n^2)