Big O and Proofs

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

Leave a Reply

Your email address will not be published. Required fields are marked *