Week 1: C++ basics and Time Complexity

Rabbit hole sheet

Go in order: each question leads to the next. Tick one off when you can answer it in your own words.

1. 1.What's the difference between O(n) and θ(n)?
2. 2.Wait, what is that θ symbol even doing there?
3. 3.So what the hell are Big-O, Big-Theta and Big-Omega actually?
4. 4.Are these supposed to be used strictly according to their mathematical definitions, or is everyone just winging it?
5. 5.If they're strict, why do CP people keep saying "O(n)" when they basically mean θ(n)?
6. 6.Is that actually the standard convention nowadays, or did we just collectively decide this is fine?
7. 7.Is there some class of algorithms where this convention breaks, and O is actually being used as a proper upper bound?
8. 8.What makes those cases different from the usual CP usage?
9. 9.Is there a difference between how complexity is mathematically derived and how people casually report it?
10. 10.So when someone says "this is O(f(n))", what are they actually trying to tell me depending on the context?

Problems

Problems will be added after the session.