Asymptotics

In this topic we will learn how to compare the performance of algorithms on large inputs using asymptotic notations — the Big Oh and the Big Omega. In our examples, we will mainly deal with running times of algorithms (so-called time complexity); analogously one can analyze memory usage (so-called space complexity), too. We will also investigate how the success probability of an algorithm can depend on input size or security parameters using the concepts negligible, overwhelming and noticeable.