patternMinor
What does $\omega{(1)}\cdot O(logN)$ mean?
Viewed 0 times
omegawhatmeanlogncdotdoes
Problem
What does $\omega{(1)}$ mean as a factor?
In some papers, there exists some asymptotic analysis which comprises a product of multiple Landau notation like $\omega(1)\cdot O(logN)$.
In this example, what is the meaning of the additional factor $\omega(1)?$
In some papers, there exists some asymptotic analysis which comprises a product of multiple Landau notation like $\omega(1)\cdot O(logN)$.
In this example, what is the meaning of the additional factor $\omega(1)?$
Solution
It presumably means a product of the form $f(N)\,g(N)$, where $f(N)\in\omega(1)$ and $g(N) \in O(\log n)$.
However, that's a very strange thing to write, since every well-behaved function $h$ can be written in this way. If $h\in\omega(1)$, write it as $h(N)\cdot1$, which is valid, since $1\in O(\log N)$; if $h\in O(1)$, write it was $N\cdot (h(N)/N)$.
However, that's a very strange thing to write, since every well-behaved function $h$ can be written in this way. If $h\in\omega(1)$, write it as $h(N)\cdot1$, which is valid, since $1\in O(\log N)$; if $h\in O(1)$, write it was $N\cdot (h(N)/N)$.
Context
StackExchange Computer Science Q#81755, answer score: 6
Revisions (0)
No revisions yet.