3
$\begingroup$

I have a data structure that can perform a task $T$ in constant time, $O(1)$. However, every $k$th invocation requires $O(\log{n})$, where $k$ is constant.

Is it possible for this task to ever take amortized constant time, or is it impossible because the logarithm will eventually become greater than $k$?

If an upper bound for $n$ is known as $N$, can $k$ be chosen to be less than $\log{N}$?

$\endgroup$
  • 2
    $\begingroup$ It depends on how $k$ relates to $n$. For instance $k=2$ then this will not matter and $n$ operations will take $O(n \log n)$. If $k = n$ then after $n$ operations we have time $O(n + \log n)$. How does $k$ relate to $n$? $\endgroup$ – ryan Apr 14 at 20:09
  • $\begingroup$ @ryan k is constant. (I have edited the question to specify this) $\endgroup$ – rtheunissen Apr 14 at 21:04
8
$\begingroup$

If every $k$th operation takes $O(\log n)$ time, then the best bound you can get on the amortized complexity is $O(1 + \frac{\log n}{k})$. This follows from the definition of amortized complexity.

$\endgroup$
  • $\begingroup$ Does that mean that if k is constant, the amortized complexity is O(1 + (log n / k))? $\endgroup$ – rtheunissen Apr 14 at 21:05
  • 8
    $\begingroup$ If $k$ is constant, the amortized complexity is $O(\log n)$. $\endgroup$ – Yuval Filmus Apr 14 at 21:07
  • $\begingroup$ @YuvalFilmus might want to note that this is per step, the overall complexity cannot be better than O(n) $\endgroup$ – Frank Hopkins Apr 14 at 23:46
  • $\begingroup$ Of course, I just mean the cost of the task itself. $\endgroup$ – rtheunissen Apr 15 at 0:14

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.