big-o notation

find_the_fun

Active member
For megre sort alogirthm the runtime is T(n)=nb+cnlog(n). It's not quite clear to me why this is O(nlogn) is it because b and c are constants?

CaptainBlack

Well-known member
For megre sort alogirthm the runtime is T(n)=nb+cnlog(n). It's not quite clear to me why this is O(nlogn) is it because b and c are constants?
It is because for $$n>n_0$$ where $$n_0>0$$ is greater than the base of the logarithm (so $$\log(n)>1$$ )
:

$|T(n)|=|n \; b+c\; n \log(n)|<|b| \; n+|c|\; n \log(n)<|b|\; n \log(n)+ |c|\; n \log(n) = A\; n \log(n)$

CB

Last edited: