table of contents

<aside> 💬 why analyse algorithms? we want a way to describe how algorithms perform at scale (i.e., when we are receiving millions or billions of inputs)

</aside>

we can runtime $T$ is a function of the input size $n$ —> we can write this as $T(n)$

big-O notation answers the question❓

What is the relationship between the runtime of our algorithm and the size of its input?

or in other words…

How does the runtime of our algorithm increase as input increases to very large amounts?

note: we can also use big-O notation to describe memory usage of an algorithm (called space complexity), but in COMP2521 we care more about time

when describing performance of an algorithm using big-O notation, we disregard the coefficients and lower order terms and just focus on the highest order (dominant) term

e.g. $O(5n^2 + 3n+600)$ is just expressed $O(n^2)$

e.g. $O(n^3 + 4 n^2 \log n + 8000n)$ is just expressed as $O(n^3)$

Time Complexity Big-O Notation
constant $O(1)$
logarithmic $O(\log n)$
linear $O(n)$
quasilinear $O(n \log n)$
quadratic $O(n^2)$
exponential $O(2^n)$
factorial $O(n!)$
$O(n^n)$