Big O Notation Flashcards
1
Q
Big O Notation
A
- counting number of simple operations the computer has to perform
- allows us to talk about how the runtime of an algorithm grows as the inputs grow
- worst case scenario
- doesn’t depend on the hardware (only algorithms)
2
Q
counting operations
A
counting each operator
3
Q
f(n) could be linear
A
f(n) = n
4
Q
f(n) could be quadratic
A
f(n) = n^2
5
Q
f(n) could be constant
A
f(n)=1
6
Q
constant
A
- arithmetic operations
- variable assignments
- accessing elements in an array by index or object by key
7
Q
time complexity
A
how to analyze the runtime of an algorithm as the size of the inputs increase
8
Q
space complexity (auxiliary)
A
how much additional memory do we need to allocate in order to run the code in our algorithm
9
Q
constant space
A
- most primitives (booleans, numbers, undefined, null)
10
Q
O(n) space
A
- strings (where n is string length)
- reference data types (n is length of arrays and number of keys in objects)
11
Q
logarithms or log
A
- the power to which a number must be raised in order to get some other number
- roughly measures the number of times you can divide that number by 2 before you get a value that’s less than or equal to one (ex. log(8) = 3)
12
Q
log2(8) = 3
A
2 to what power equals 8 (answer: 3 or 2^3 = 8)
13
Q
logarithmic time complexity
A
searching algorithms, efficient sorting algorithms, recursion (sometimes)
