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}$?

  • 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 '19 at 20:09
  • $\begingroup$ @ryan k is constant. (I have edited the question to specify this) $\endgroup$ Apr 14 '19 at 21:04

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.

  • $\begingroup$ Does that mean that if k is constant, the amortized complexity is O(1 + (log n / k))? $\endgroup$ Apr 14 '19 at 21:05
  • 8
    $\begingroup$ If $k$ is constant, the amortized complexity is $O(\log n)$. $\endgroup$ Apr 14 '19 at 21:07
  • $\begingroup$ @YuvalFilmus might want to note that this is per step, the overall complexity cannot be better than O(n) $\endgroup$ Apr 14 '19 at 23:46
  • $\begingroup$ Of course, I just mean the cost of the task itself. $\endgroup$ Apr 15 '19 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.