# Asymptotics, Growth, and Decay

When considering stuff like the security and efficiency of algorithms and procedures, and in particular cryptographic schemes and block chains, we need a way to relate them to the various parameters. Consider for example a procedure that *sorts* an array: it is given a list of numbers, and returns them in increasing order. How can we describe "how fast" that procedure is? We can ask how fast it takes to sort ten numbers, or twenty, but that won't tell us much if in the future we want to use it to sort 1357 or 20545 numbers. We need some way to talk about how the length of the computation *grows*.

For this we use a *function* $$f$$ that is given the *input length* $$n$$ and outputs "how long" it would take to sort an array of this size.

Now, the term "how long" is also ill conceived. How do we count? In seconds? CPU cycles? Don't all such metrics depend on the computer running it? Can't they be different for two different lists with the same length?

The answer to all of that is yes. The whole point of discussing *growth* is to put that aside, and just look at the *trajectory*. This is often called the *asymptotics* of the function.

It is true that the asymptotics doesn't have *all* the information, but it tells us what happens in the long run. That "other part", that doesn't tell us about the *rate* of growth, but gives us *concrete numbers* (which is often just referred to as "the constants"), is also very important. But from some vantages, like the one permeating most of this book, the asymptotic point of view is the appropriate one.

## Asymptotic Notation

To streamline the notations, computer scientists came up with a bit confusing yet very powerful notational system that captures the "type of growth" of the function while ignoring everything else.

Say that $$f$$ is some function that interests us, like the runtime of a sorting algorithm given the length $$n$$ of the list it needs to sort. As we said, $$f$$ is quite complicated and not even completely defined. However, we can say something like $$f$$ grows "at most linearly". What do we mean by that? That while $$f$$ might be a bit erratic and unexpected, we know that there is a function that *looks like a line* such that $$f$$ is *almost always* below it. This would look something like this:

<figure><img src="/files/oRJoLJ7p2D2VhIkbtnzs" alt=""><figcaption><p>Illustration of <span class="math">f=O(n)</span>, the red line is the function <span class="math">2n+6</span></p></figcaption></figure>

We use the notation $$f=O(n)$$ to say that there is *some line* such that $$f$$ is below it *from some point onward*. In other words, we say that $$f=O(n)$$ if there exist two numbers $$m$$ and $$b$$ such that for any *sufficiently large* $$n$$ we have that $$f(n) < mn + b$$. Note that the notation $$f=O(n)$$ *hides* the actual numbers $$m,b$$ and only tells us they exist. *This* is the power of asymptotic notation, it *hides the constants* and allows us to *qualitatively* talk about the growth *trend*. So yeah, the constants may *change* based on the exact architecture of the system that will eventually run the code, but for any system there will be *some* constants fitting the bill, and *that* is what captured by this notation.

This is often called the *big oh* notation.

**Exercise**: Prove that $$n^2 \ne O(n)$$

<details>

<summary>Solution</summary>

Say that $$n^2 = O(n)$$, then there are some $$m$$ and $$b$$ and $$N$$ such that for any $$n>N$$ we have that $$n^2 < mn+b$$. Dividing both sides by $$n$$ we get that $$n < m + \frac{b}{n}$$. However, for $$n>b$$ we have that $$m+\frac{b}{n} < m+1$$, but $$m+1$$ is a constant so we can't have that $$n\<m+1$$ for *all* sufficiently large $$n$$.

</details>

More generally, given two functions $$f$$ and $$g$$ we can denote $$f=O(g)$$ to mean that there are some constants $$m$$ and $$b$$ such that, for sufficiently large $$n$$, it holds that $$f(n)\le m\cdot g(n) + b$$. This allows us to write stuff like $$f = O(n^2)$$ to say "look, I can't tell you *exactly* how $$f$$ grows, but the rate at which it grows is at most quadratic, if you put in an input three times longer, the growth in runtime is at most by a factor of three squared, that is nine".

**Exercise**: Prove that $$n^2 = O(n^3)$$. More generally, prove that if $$a$$ and $$b$$ are natural numbers then $$n^a = O(n^b)$$ if and only if $$a\le b$$.

Like the big oh notation helps us bound things from above, we have the *big omega* notation to bound things from *below*. By writing that $$f(n) = \Omega(n)$$ we say that $$f$$ grows *at least linearly*, but it could actually grow faster, just like a *sub*linear function is still $$O(n)$$.

**Exercise**: Write a formal definition for $$f=\Omega(g)$$

<details>

<summary>Solution</summary>

There are some constants $$m$$ and $$b$$ such that, for sufficiently large $$n$$, it holds that $$f(n)\ge m\cdot g(n) + b$$.&#x20;

</details>

Finally, we have the *theta* notation, which we use to say that we know *exactly* what the asymptotics are. In brief, we write that $$f = \theta(g)$$ if it holds that *both* $$f = O(g)$$ *and* $$f =\Omega(g)$$. The notation $$f=\theta(g)$$ essentially means "we might not know what $$f$$ is, but as long as we talk about growth rate, we can just pretend that it is $$g$$". Typically, $$g$$ will be much simpler than $$f$$. For example, $$f$$ could be the running time of some complex algorithm, or the probability to revert a transaction in some concrete protocol, and instead of computing $$f$$ explicitly we could just prove that, say, $$f = \theta(n^2)$$.

**Exercise**: A function $$f$$ is called *bounded* if there is some $$B$$ such that $$f(n) < B$$ for all $$n$$. Let $$f$$ be bounded and let $$g$$ be any function, prove that $$f\cdot g = \theta(g)$$.

**Exercise**: Find a function $$f$$ that is *not linear*, but such that $$f=\theta(n)$$.

Sometimes we don't care about *growth* but about *decay*. That is, we want to know how *small* $$f$$ gets as $$n$$ increases. For example, $$f$$ could be the probability that an attacker manages to break your encryption as a function of the length of your secret-key. We can do it using the same notation. For example, $$f(n) = O(1/n)$$ is what we mean when we say that a function *decays linearly*.

## Exponentials

Exponentials and logarithms are how we typically describe things that are *lar*ge or *small*. Note that I did not end the latest sentence with "respectively", and this is no coincidence. When we talk about *growth* (that is, how fast things go *to infinity*), exponential growth is large, while logarithmic growth is *very slow* (and in between we have e.g. the *polynomial* growth: linear, quadratic, quartic, etc...). When we talk about *decay* (that is, how fast things go to *zero*), then exponential decay is *small*.

As an example, consider generating a secret-key. In any encryption scheme, a secret-key can be represented as a *uniformly random* string of bits, where the length is chosen by the user. Say we use a key of length $$n$$, then how many possible keys are there? The first bit is either $$0$$ or $$1$$, so two options. The second bit is either $$0$$ or $$1$$ too, so two more options *on top* of each of these two options, leading to four options, and so on. It is easy to get convinced that the number of possible keys is $$2^n$$. Hence, the number of keys *grows exponentially with* $$n$$.

Now say I am trying to *guess* your secret key. Since all the bits are uniformly random, we get that they are all *equally likely*, so that the probability I guess correctly (no matter how I guess) is one in $$2^n$$, that is, $$1/2^n$$ which is also commonly written as $$2^{-n}$$. So since the possible number of keys *grows exponentially* (and the keys are uniform), then the probability to guess a key *decays exponentially*.

To be more concrete, we say that $$f$$ is *exponential* if there is some constant $$c>0$$ such that $$f=\theta(e^{cn})$$ where $$e$$ is the infamous [Euler's number](https://en.wikipedia.org/wiki/E_\(mathematical_constant\)). Why $$e$$ and not any other number? Because it is comfortable. The fact is that for any number $$b$$ there is a number $$c$$ such that $$b^n = e^{cn}$$. (This number $$c$$ is called the *natural logarithm* of $$b$$, denoted $$\ln b$$, and we will discuss it shortly.) So you can replace $$e$$ with any positive number larger than $$1$$ and obtain a completely equivalent definition.

**Exercise**: Let $$b>1$$, let $$f$$ satisfy that there is some $$c>0$$ such that $$f=\theta\left(b^{cn}\right)$$, prove that $$f$$ is exponential.

## Logarithms

## Negligible Functions


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://shai-deshe.gitbook.io/understanding-blockdags-and-ghostdag/supplementary-material/math/stuff-you-should-know/asymptotics-growth-and-decay.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.