Big Oh! (Week 11)
Hey! This week we looked further into Big Oh and run times.
Last week, we defined Big Oh as:
t e O(g) if there are positive constants c and B so that for every natural number n no smaller than B, t(n) <= cg(n)
Using the Big Oh theorem, we can derive that if t e O(n), then t e O(n^2). This then can be extrapolated to show that O(1) is a subset of O(lg(n), which is a subset of O(n), which is a subset of O(n^2), which is a subset of O(n^3), and so on.
Big Oh is a way of showing us run time. If a function’s run time is in O(n), we can assume it will take n steps. If it’s run time is in O(lg(n)), we can assume it will take lg(n) steps. An example of code run time (in iteration, in this case) can be looked at as follows:
The code above has a run time in O(n^5). This is because the first while loop will run in n^3 steps, and the second will run in n^2 steps, however, when nested as shown, the n^2 step loop will run n^3 times, meaning it will run n^2 x n^3 times, that being n^5.
A summary of the Big Oh theorem with respect to different statements in code is as follows:
# sequences: max(O(each statement))
# loops: product of iteration of each loop (what we looked at above)
# conditions: worst possible case.