1
$\begingroup$

Usually, at least in Computer Science, $f(x) = \Omega(g(x))$ if $ \exists C > 0, \exists x_0 : \forall x \geq x_0 : f(x) \geq C g(x)$

i.e. for large values of x, $f(x)$ is at least as big as some constant times $g(x)$.

But what if I have a function which increases, the smaller the parameter $x \geq 0$ is?

For example for x denoting the side of a square, and $f(x)$ denoting be the number of $x \times x$ squares to be packed in some larger $C \times C$ square.

Using the above definition is it formally correct (and why) to claim that I can pack $\Omega(1/x^2)$ many small squares into the large one?

$\endgroup$

1 Answer 1

1
$\begingroup$

yes it is valid, it means that there is $K,\epsilon$ such that when $x<\epsilon$, your number is at least $\frac{K}{x^2}$.

The notations $O()$, $o()$, $\Theta()$, $\Omega()$, are always depending of a variable going to a limit. Usually it is $n\to\infty$, but it can be used for instance with $x\to 0$, it just needs to be clear from context without ambiguity.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .