#bigoh

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)

В эту среду, 24 апреля, Василий Наквасюк начал серию коротких докладов про алгоритмы, сложность алгоритмов, структуры данных, виды алгоритмов (сортировка, ...) и т.п. В первом докладе постарался быстро рассказать про вычислительную сложность алгоритмов и нотацию "О-большое" на примерах.

Смотреть презентацию