2
$\begingroup$

Let's say I have a discrete structure of size $n$, and some characteristic $a$ of that structure for which it holds that $a= \omega(1)$.

Is this equivalent to say that $a$ can not be a constant but it has some dependence on $n$?

  • 0
    First write down the definition of $\omega(1)$. Then look for a "characteristic" not satisfying it.2012-12-01

1 Answers 1

0

$f(n)=\omega(g(n))$ means that $ \lim_{n \to \infty}\frac{f(n)}{g(n)}=\infty $. $\omega(1)$ means that $f(n)$ is asymptotically larger than constant, i.e. $f(n)=\log n$ or $f(n)= n$