Timeline for If a function $f(n)=\Theta(g(n))$, does it follow that $f(n/k)=\Theta(g(n))$ for a constant $k$?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 21, 2020 at 10:10 | history | edited | zkutch | CC BY-SA 4.0 |
added 257 characters in body
|
| Sep 21, 2020 at 10:03 | comment | added | zkutch | @Aaron Rotenberg. Ambiguity of sentence is author's responsibility, not reader's. When you wrote "rounded" you should specify which one of all existing rounding methods you mean or, without it, you have pretension about proof for all known rounding methods. Author should provide well written text and clearly eliminate ambiguities and I am not speaking about some type of article, but, even, simple homework. | |
| Sep 21, 2020 at 9:52 | history | edited | zkutch | CC BY-SA 4.0 |
added 167 characters in body
|
| Sep 21, 2020 at 3:16 | comment | added | Aaron Rotenberg | Certainly true, in a very literal sense. But my point is that I don't think that would ever be relevant in e.g. a conference-level CS paper, because it is usually assumed that big-O notation in a complexity context can be treated as applying to functions of type $\mathbb{N} \rightarrow \mathbb{N}$ and an argument such as $n/2$ is rounded in some fashion that has no bearing on correctness. It's like arguing that a formula is wrong because the nested fraction notation $a/b/c$ is ambiguous: if it wasn't clear from context, the author shouldn't have done that. | |
| Sep 21, 2020 at 3:09 | comment | added | zkutch | @Aaron Rotenberg. This example gives you possibility to imagine function which is undefined, for example, on middle of each interval $(n,n+1)$ and defined on ends of it. Here vanishes your argument about finite set, when first one is very restrictive. | |
| Sep 21, 2020 at 2:56 | comment | added | Aaron Rotenberg | This doesn't seem super relevant, because (1) we usually assume total monotone-increasing natural number functions when working with big-O notation for program complexity, with rounding of real functions being fudged into meaninglessness by the hidden constants; and (2) big-O is all about limits, so behavior at a finite set of inputs doesn't really matter. | |
| Sep 21, 2020 at 2:42 | history | answered | zkutch | CC BY-SA 4.0 |