Big O

Question 1

What is Big O and why is it important

Answer 1

Big O time is the language and metric we use to describe the efficiency of algorithms. no knowing this concept can severely hurt you when developing an algorithm

Question 2

O(N)

Answer 2

asymptotic runtime increases linearly with the amount of work to be done

Question 3

O(1)

Answer 3

Time taken to complete a task, no matter how large it gets is constant.

Question 4

Academic definition of big O

Answer 4

Big O describes an upper bound on the time it takes to complete a task. Think of it as “ the algorithm is at least as fast as x run time”

Question 5

Academic definition of Big Omega

Answer 5

Big Omega is like Big O but for a lower bound on runtime. can be thought of as “ the algorithm wont be faster than x runtime”

Question 6

Academic definition of Big Theta

Answer 6

Big Theta is both big O and big Omega. ie an algorithm is Theta(N) if it is both O(N) and Omega(N). Theta gives a tight bound on runtime.

Question 7

Best case

Answer 7

The case that the algorithm runs that gives the lowest/ fastest runtime.

Question 8

worst case

Answer 8

a case in which the algorithm takes the maximum amount of time it can to solve a problem.

Question 9

Expected case

Answer 9

the run time that an algorithm usually takes

Question 10

Utility of the cases

Answer 10

Best case is rarely used. Usually, expected case and worse case are the same. if they are not, both need to be independently described

Question 11

what is the relationship between best/worse/expected case and bigO/Theta/Omega?

Answer 11

Best/worse/expected cases describe the Big O time for particular inputs or scenarios
BigO/Omega /Thetadescribe the upper, lower and tight end bounds for runtime

Question 12

Space Complexity

Answer 12

a measurement of the space required by an algorithm

Question 13

Tips about space complexity

Answer 13

actually allocating space in memory effects complexity, but so do function calls where the function is placed on the stack. if the function is not placed on the stack, then it does not effect complexity

Question 14

Drop the constants when using Big O

Answer 14

O(2N) becomes O(N),

Question 15

Drop non-Dominant terms

Answer 15

always drop non dominant terms
O(N^2 + N ) becomes O(N^2)
O(N + logN) becomes O(N)

Question 16

Multipart algorithms: add vs multiply

Answer 16

add runtimes when work is successive: example: two for loops (for loop a and b) execute one right after another. The total amount of work here is O(a+b)

Question 17

Multipart algorithms: add vs multiply

Answer 17

multiply run times when algorithm is of the form “ do this for each time you do that” ie a for loop inside a for loop

Question 18

Amortized run time makes no sense. Look it up

Answer 18

please

Question 19

Log N run times

Answer 19

occurs when the number of elements in the problem space gets halved each time. Think Binary search

Question 20

Recursive runtimes

Answer 20

Often, but not always, the run time will be O(branches ^depth)