4
$\begingroup$

If I can easily state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, the number of steps is $n\log n$, is this enough to allow me to state the complexity is amortized $O(n\log n)$?

I have a tree building algorithm - when adding elements a rebalancing operation occurs every so often, with those operations getting progressively more expensive as the tree size grows close to a power of two elements (before becoming cheaper again once we pass such a power). At every power of two elements its easy to state the number of steps done so far but in between it's not so easy.

I'm slightly embarrassed by this question as I currently assume it is OK to state an amortized time of $O(n\log n)$ for this situation but my conclusions, from reading a discussion elsewhere (see next part), seemed to contradict this.


Update: I've move the second part of part of this question, relating to Conc-tree lists and my confusion over how such trees could be built in $O(n)$, into a separate question.

$\endgroup$
1
  • $\begingroup$ No! $\endgroup$ – Raphael Nov 7 '16 at 10:37
4
$\begingroup$

You are asking several questions. I will only answer some of them.

Suppose that the running time of an algorithm as a function of $n$ satisfies $T(2^k) = O(2^k \log 2^k)$. Is it true that $T(n) = O(n \log n)$? Without any more information on the running time, this is patently false. For example, consider the function $$ T(n) = \begin{cases} n\log n & \text{if $n$ is a power of $2$}, \\ n^2 & \text{otherwise}. \end{cases} $$ However, in many cases we would expect $T$ to be monotone in $n$. In that case, the deduction does hold. Suppose that $T(n) \leq Cn\log n$ whenever $n$ is a power of $2$. Given arbitrary $n$, we can find $m \leq 2n$ which is a power of $2$, and then $$ T(n) \leq T(m) \leq Cm\log m \leq 2Cn \log n + O(n) = O(n\log n). $$

Suppose now that there is a data structure such that the first $n$ operations take time at most $Cn$ whenever $n$ is a power of $2$. If we let $T(n)$ denote the maximal time that $n$ operations take, then $T$ satisfies the conditions stated above (in particular, monotonicity is built-in), and so the amortized time per operation is indeed $O(1)$. Your case is a bit more complicated since different operations have different amortized running times, but the conclusion should be the same.

$\endgroup$
1
  • $\begingroup$ Thanks Yuval - that's very nicely explained. In the question I said I felt embarrassed asking about something that I assumed to be correct - now I feel embarrassed for assuming something that you've so clearly shown to be incorrect :) I've split out the second part of my question (about conc-lists) into a separate question (though I worry it'll get 0 views as the subject line on its own sounds stupid). $\endgroup$ – George Hawkins Nov 5 '16 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.