Big O & Space Complexity

Question 1

Big O Complexity Chart

(Name the different O calculations)

( 7 total )

Answer 1

how does the runtime grow as the input increases

refer to image

Question 2

Big O Rules

how to simplify the calculations/notations?

(4)

Answer 2

1. Worst Case: calculates based on the worst case outcome, becuase the input is unknown. Ex. find a name in a for loop. The name could be anywhere in the list/array so you assume you have to look at each item before you find the person you are looking for.
2. Remove Constants: remove the numbers from the calculation. Ex. O(n/3 + 500) becomes O(n)
3. Different Terms for Inputs: n becomes a + b when looping through more than one input variable. O(a + b)
4. Drop Non Dominant (Terms): remove the calculation that has the lowest impact on size of the output. Ex. O(n + n^2) becomes O(n^2); n + has way less impact on the size of the output so it is removed.

Question 3

O(n)

definition

when is it applied?

Answer 3

linear growth rate on a graph

there is one operation for every data input

n refers to the number of inputs, this calculation is saying the big O depends on the number of inputs

usually applies to for loops

also applies to loops within loops

Question 4

O(1)

definition

Answer 4

constant time

flat line, no matter the inputs you are performing one operation

ex. grabbing the first item in the array

Question 5

O(a + b)

O(a * b)

Answer 5

• O(n) for two different input variables.
• When you have two inputs the same level of indentation add.
• O(a * b) when the variables are nested

Example:

// two input variables

function compressBoxesTwice(boxes, boxes2) {

boxes. forEach(function(boxes) {
console. log(boxes);

});

boxes2. forEach(function(boxes) {
console. log(boxes);

});

}

// the Big O Notation would be O(a + b)

Question 6

O(n^2)

Answer 6

used for nested loops; O( n * n ) multiple when different levels of indentation

for every (n) element the operations increase quadratically

comes up a lot in interviews; converting an algorithmn that is O(n^2) into a faster running algorithmn

if you have more than one nested loop you are probably doing something wrong, it scales horribly

Question 7

O(log N)

Answer 7

used alot for searching algorithms

example binary search

usually each search algorithmn has log n if they are sorted

Question 8

O( n * log(n) )

Answer 8

used for sorting algorithms

Question 9

O(2^n)

Answer 9

used for recursive algorithms

Question 10

O(n!)

Answer 10

factorial for addng a loop for every every element in a data structure

nested loop for every input

Question 11

4 Elements that cuase time in a function

(contributors to the Big O calculation)

Answer 11

1. Operations: ( + - * / )
2. Comparisons: ( ==)
3. Looping: for & whole loops
4. Outside function call: function calling another function

Question 12

3 Pillars of Coding

what 2 componenets drive scalability

tradeoff issue to be aware of

Answer 12

3 Pillars of Code

1. readable code (clean)
2. speed (time complexity that is efficient)
3. memory (space complexity - what is the memory usage)

Speed & Memory are the two componenets of scalability

There may be a tradeoff between the 3

• optimizing for time might impact space
• optimizing for readability might impact the other 2

Question 13

causes of space complexity

Answer 13

1. variables
2. data structures
3. function call
4. allocations

Question 14

Two Big O Notations that Generally Occur in Space Complexity

Answer 14

• O(n): you are adding memory within a function
• O(1): you are not adding memory

O(n) Example:

def func(n) :

hi_list = []

for i in range(n) - 1 :

hi_list [i] = ‘hi’

return hi_list

O(1) Example:

def func(n) :

for i in range(n) - 1 :

print( ‘hi’)