2

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$?

jack
  • 23
  • 2
  • First write down the definition of $\omega(1)$. Then look for a "characteristic" not satisfying it. – GEdgar Dec 01 '12 at 20:38

1 Answers1

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$

Alex
  • 19,262