So I started 2 of the 3 pre-requisite courses I need to get accepted into a PhD program. It’s been 10 years but now I’m re-learning Java, Big O, and everything fun so here’s some info.
To keep it ultra simple:
1. find a T(n) that describes how many steps it takes to run your algorithm
2. if you are trying to prove your algorithm is O(g(n)) find an M such that T(n) <= M * g(n) for all sufficiently large n
** O(g(n)) is just a place holder for what you’re trying to move, complexity class **
you can just take the leading coefficient, add 1 to it, and there is your M
for instance, with our example, we had T(n) = 3 * n + 4
the leading coefficient was 3, so we could choose M = 4