Why the height complexity of a data structure, generally expressed in terms of $\log n$, do not contain a ceiling or floor ?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ What is the "height complexity of a data structure"? Do you mean the height of a tree? $\endgroup$– quicksortCommented Jan 16, 2017 at 10:43
-
3$\begingroup$ O(log n) = O(log n + 1) $\endgroup$– CalethCommented Jan 16, 2017 at 10:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Asymptotically, $\log n$ and $\lfloor \log n \rfloor$ (or $\lceil \log n \rceil$) are the same: a function is $\Theta(\log n)$ iff it is $\Theta(\lfloor \log n \rfloor)$. Therefore there is no need for floor or ceiling.
answered Jan 16, 2017 at 11:02
-
$\begingroup$ Thank you. I was talking about a non-asymptotic complexity. $\endgroup$– user7060Commented Jan 16, 2017 at 11:24
-
$\begingroup$ If you want an exact number, then you should definitely use floor or ceiling. Otherwise, they are not necessary, since they only change the value by at most a constant (in fact, by at most 1). $\endgroup$ Commented Jan 16, 2017 at 13:04
-
$\begingroup$ Thank you @YuvalFilmus I was asking this question because sometimes I see (non asympotic) analysis in which the ceil or floor is omitted. $\endgroup$– user7060Commented Jan 18, 2017 at 10:08
-
$\begingroup$ They are probably being a bit sloppy. It's nicer to the eyes without floors or ceilings. $\endgroup$ Commented Jan 18, 2017 at 10:13