Big O Notation Flashcards
What is Big O notation?
Big O notation is the language we use for articulating how long an algorithm takes to run. It’s how we compare the efficiency of different approaches to a problem.
What affects how quickly the runtime grows?
Some external factors affect the time it takes for a function to run: the speed of the processor, what else the computer is running, etc. So it’s hard to make strong statements about the exact runtime of an algorithm. Instead we use big O notation to express how quickly its runtime grows.
How is it relative to the input?
Since we’re not looking at an exact number, we need something to phrase our runtime growth in terms of. We use the size of the input. So we can say things like the runtime grows “on the order of the size of the input” (O(n)) or “on the order of the square of the size of the input” (O(n^2)).
What happens as the input gets arbitrarily large?
Our algorithm may have steps that seem expensive when n is small but are eclipsed eventually by other steps as n gets huge. For big O analysis, we care most about the stuff that grows fastest as the input grows, because everything else is quickly eclipsed as n gets very large. If you know what an asymptote is, you might see why “big O analysis” is sometimes called “asymptotic analysis.”
What is the difference between the function running in O(1) time (or “constant time”) and the function running in O(n) time (or “linear time”)?
function printFirstItem(arrayOfItems) {
console.log(arrayOfItems[0]);
}
This function runs in O(1) time (or “constant time”) relative to its input. The input array could be 1 item or 1,000 items, but this function would still just require one “step.”
function printAllItems(arrayOfItems) {
arrayOfItems.forEach(function(item) {
console.log(item);
});
}
This function runs in O(n) time (or “linear time”), where nn is the number of items in the array. If the array has 10 items, we have to print 10 times. If it has 1,000 items, we have to print 1,000 times.
What does a function look like if it’s running in in O(n^2) time (or “quadratic time”)?
function printAllPossibleOrderedPairs(arrayOfItems) {
arrayOfItems.forEach(function(firstItem) {
arrayOfItems.forEach(function(secondItem) {
console.log(firstItem, secondItem);
});
});
}
Here we’re nesting two loops. If our array has n items, our outer loop runs n times and our inner loop runs n times for each iteration of the outer loop, giving us n^2 total prints. Thus this function runs in O(n^2) time (or “quadratic time”). If the array has 10 items, we have to print 100 times. If it has 1,000 items, we have to print 1,000,000 times.
Why can we get away with dropping the constants when you’re calculating the big O complexity of something?
For big O notation we’re looking at what happens as n gets arbitrarily large. As n gets really big, adding 100 or dividing by 2 has a decreasingly significant effect.
Why can we get away with dropping the less significant terms when you’re calculating the big O complexity of something?
We can get away with this because the less significant terms quickly become, well, less significant as n gets big.
How to optimize for using less memory instead of (or in addition to) using less time?
We look at the total size (relative to the size of the input) of any new variables we’re allocating.
This function takes O(1) space (we aren’t allocating any new variables):
function sayHiNTimes(n) {
for (var x = 0; x < n; x++) {
console.log('hi');
}
}
This function takes O(n)O(n) space (the size of hiArray scales with the size of the input):
function arrayOfHiNTimes(n) {
var hiArray = [];
for (var i = 0; i < n; i++) {
hiArray[i] = 'hi';
}
return hiArray;
}
When speaking to space complexity, do are we referring to additional space or constant space?
Usually when we talk about space complexity, we’re talking about additional space, so we don’t include space taken up by the inputs. For example, this function takes constant space even though the input has n items:
function getLargestItem(arrayOfItems) {
var largest = 0;
arrayOfItems.forEach(function(item) {
if (item > largest) {
largest = item;
}
});
return largest;
}
Downsides of Big O
- Big O ignores constants, but sometimes the constants matter. If we have a script that takes 5 hours to run, an optimization that divides the runtime by 5 might not affect big O, but it still saves you 4 hours of waiting.
- Beware of premature optimization. Sometimes optimizing time or space negatively impacts readability or coding time. For a young startup it might be more important to write code that’s easy to ship quickly or easy to understand later, even if this means it’s less time and space efficient than it could be.
Logarithm Definition
A Logarithm is asking: “What power must we raise this base to, in order to get this answer?”
So if we say:
\log_{10}{100} log
10
100
The 10 is called the base (makes sense—it’s on the bottom). Think of the 100 as the “answer.” It’s what we’re taking the log of. So this expression would be pronounced “log base 10 of 100.”
And all it means is, “What power do we need to raise this base (1010) to, to get this answer (100100)?”
10^x = 100 10
x
=100
What xx gets us our result of 100100? The answer is 22:
10^2 = 100 10
2
=100
So we can say:
\log_{10}{100} = 2 log
10
100=2
What are logarithms are used for?
The main thing we use logarithms for is solving for x when x is in an exponent.
So if we wanted to solve this:
10^x = 100 10
x
=100
We need to bring the xx down from the exponent somehow. And logarithms give us a trick for doing that.
We take the \log_{10}log
10
of both sides (we can do this—the two sides of the equation are still equal):
\log_{10}{10^x} = \log_{10}{100} log
10
10
x
=log
10
100
Now the left-hand side is asking, "what power must we raise 1010 to in order to get 10^x10
x
?" The answer, of course, is xx. So we can simplify that whole left side to just "xx":
x = \log_{10}{100} x=log
10
100
We’ve pulled the xx down from the exponent!
Now we just have to evaluate the right side. What power do we have to raise 1010 to do get 100100? The answer is still 22.
x = 2 x=2
Logarithm rules
Simplification: log_{b}{(b^x)} = x: Useful for bringing a variable down from an exponent.
Multiplication: log_{b}{(x*y)} = log_{b}{(x)} + log_{b}{(y)}
Division: log_{b}{(x/y)} = log_{b}{(x)} - log_{b}{(y)}
Powers: log_{b}{(x^y)} = y * log_{b}{(x)}
Change of base: logb (x)=logc (b)/logc (x): Useful for changing the base of a logarithm from b to c.
Where logs come up in algorithms and interviews
“How many times must we double 1 before we get to n” is a question we often ask ourselves in computer science. Or, equivalently, “How many times must we divide n in half in order to get back down to 1?”
Can you see how those are the same question? We’re just going in different directions! From n to 1 by dividing by 2, or from 1 to n by multiplying by 2. Either way, it’s the same number of times that we have to do it.
The answer to both of these questions is log_{2}{n}log
2n.
