Another slow day. I covered some more Big O Notation and worked on some more example problems. I learned a while back that a key to success is being able to get through the slow days just like you would the exciting ones. Sometimes you need slow days to help you get ready for what’s to come.

TLDR;

Okay, so here are the highlights of what I did:

• Still reading through the Big O notation section in “Cracking the Coding Interview” by Gayle L. McDowell. I went through a few more example problems. They are starting to get more advanced. Still nothing super complicated but I have had more questions come up in my mind than yesterday’s examples. For example: does O(x!) mean a recursive function or is it a factorial function? I got a bit confused about that.
• I tried out a few resources for additional Big O Notation Practice Problems. So far nothing has stood out as being exceptional. I will still keep looking for something that I think is very beneficial.

Notes on Big O Notation

Drop the Non-Dominant Terms

We already know that we drop constants, and constant coefficient values from Big O expressions. But what about something like this:

O(N^2 + N)

The second N is not a constant. So what do we do…?

Well… we already said that we don’t care about constant coefficient like the 2 in 2 * N^2. Another way we can represent this would be as N^2 + N^2. Well… we are fine getting rid of an N^2 so, why keep a measly N in the expression?

When writing Big O expressions we do not include the non-dominant values. We focus on the dominant or highest order values for the expression. So in the case where we have N^2 + N, we can drop the N to produce the Big O expression O(N^2) . We do this because the non-dominant term will not significantly change the complexity of the algorithm. Therefore, we do not need to represent it in our Big O expressions. Here are some more examples:

• O(N^2 + N) becomes O(N^2)
• O(N + log (N)) becomes O(N)
• O(5*2^N + 1000N^100) becomes O(2^N)

We might still use a sum in Big O expressions but it will be for expressions that contain two contributing variables that we cannot solve for further. For example, the expression O(B^2 + A) cannot be reduced further without any more knowledge about A or B

Common Big O times Graphed

Here is a list that lists common Big O times and their respective rates of increase. The list goes from the fastest (highest complexity = bad) to the slowest (lowest complexity = good). Be aware that although constant time (O(1)) is good there are times when other complexities can be faster than that constant time.

1. O(x!) (x factorial???)
2. O(2^x) (exponential)
3. O(x^2) (exponential also???)
4. O(x log (x) ) (linear times logarithmic???)
5. O(x) (linear)
6. O(log (x)) (logarithmic)

There are lots of expressions that have higher rates than O(x!). Such as O(x^x) or O(2^x * x!)

Multi-part Algorithms: Add vs. Multiply

We often must deal with algorithms with multiple steps. So… How do we represent those steps in the Big O expression? Do we multiply the steps together or do we add them? We will find out now. Below are two examples. We will compare them to see when we should add and when we should multiply the different steps involved in an algorithm to get our Big O expression.

// Example 1: Add the Runtimes O(A + B)

for (int a : arrA){
  print(a);
}

for (int b : arrB){
  print(b);
}

// Example 2: Multiply the Runtimes O(A * B)

for (int a : arrA){
  for (int b : arrB){
    print(a + "," + b);
  }
}

• In the example 1, we do A chunks of work then B chunks of work. Therefore, the total amount of work is O(A + B).
• In the example 2, we do B chunks of work for each element in A. Therefore, the total amount of work is O(A * B).

Therefore:

1. If your algorithm is in the form “do this, then, when you’re all done, do that” then you add the runtimes.
2. If your algorithm is in the form “do this for each time you do that” then you multiply the runtimes.

It’s very easy to mess this up in an interview, so be careful.

Conclusion

That’s all for today. If you are interested in the MIT course you can check out the video lecture I’m currently going through. The lecture is helpful but isn’t sufficient by itself. Anyways, until next time PEACE!