⌊1/𝑛⌋ - represents the floor function Does the floor or ceiling function affect the complexity under which a function falls?
⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛)
Found this interesting question in a Cornell paper
Thanks
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Where did you find it? I highly doubt any real paper would have anything to do with this function... $\endgroup$– nir shaharCommented Jun 15, 2021 at 10:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Neither of those. For $n>1$, $\lfloor\frac{1}{n}\rfloor=0$. Hence, $\lfloor\frac{1}{n}\rfloor=0=O(0)$.
Also, you can easily rule out $\Omega(\log(n))$ since $\log$ is an increasing to infinity, while $\frac{1}{n}$ is a decreasing function.
answered Jun 15, 2021 at 10:11
-
$\begingroup$ "Also, you can easily rule out $\Omega(\log(n))$ since $\log$ is an increasing function, while $1/n$ is a decreasing function." As stated, the argument is false, as you can have $f$ increasing and $g$ decreasing such that $g=\Omega(f)$ (e.g. $f(n)=2-1/n$ and $g(n)=2+1/n$). I'm guessing you meant "increasing to infinity", or something of the sort? $\endgroup$ Commented Jun 15, 2021 at 11:05
-
-
1$\begingroup$ At this point we get into hairsplitting. But calculating floor(1/n) requires checking whether n = 1 or not, so it's not O(0), it's only O(1). floor(1/2n) would always be zero. $\endgroup$ Commented Jun 16, 2021 at 14:16