How to write that the ratio between two functions stays the same How would I write that two functions increase at the same rate?
More specifically I'm trying to write that even tho two sortings algorithms don't produce the same output in a graph, even though they have the same time complexity $O(n^2)$, it's still valid as they increase by the same rate.
Currently, I have shown a table that dividing the function will result in 2 (+- some noise).
But I would like to show it mathematically too. My guess at the moment would be something like this, but I would like to confirm that it's correct :)
$$\lim_{x \to \infty } \frac{f(x)}{g(x)}\approx 2$$
 A: There are two different accepted notations here, and they mean slightly different things. I'll talk in terms of functions $\alpha(x)$ and $\beta(x)$.
Case 1: If you want to say "For sufficiently large $x$ we always have $\alpha(x) \le c \beta(x)$ and $\beta(x) \le d \alpha(x)$ for some constants $c,d$" then you can write $\alpha(x) = \Theta(\beta(x))$. See Wikipedia. This is useful for situations where you're claiming two functions grow at the same rate up to a constant multiplier, but you don't really care about the exact value of the constants.
Case 2: If you want to say $\lim_{x \to \infty} \frac{\alpha(x)}{\beta(x)} = 1$, then you can write $\alpha(x) \sim \beta(x)$. See Wikipedia again. This is a stronger statement: if $\alpha(x) \sim \beta(x)$ then we always have $\alpha(x) = \Theta(\beta(x))$.
Example A: If $\alpha(x) = 3x^2 + \log(x)$ then the following statements are true: $\alpha(x) = \Theta(x^2)$, and $\alpha(x) = \Theta(3x^2)$, and $\alpha(x) \sim 3x^2$. However, we do not have $\alpha(x) \sim x^2$ because the constant matters for $\sim$.
Example B: If $\alpha(x) = \left(\sin(x)+5\right)x^2 + \log(x)$ then we still have $\alpha(x) = \Theta(x^2)$ but we cannot say $\alpha(x) \sim cx^2$ for any $c$ because of the weird fluctuating multiplier in front of the $x^2$ term. This is an example of a case where the $\Theta$ notation becomes more useful than $\sim$, since for asymptotic analysis purposes you probably mainly care about bounding $\alpha(x)$ by a constant multiple of a nice function, and you probably don't care too much that the multiplier keeps fluctuating between $4$ and $6$.
