# Complexity of many constant time steps with occasional logarithmic steps

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

• 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$? – ryan Apr 14 at 20:09
• @ryan k is constant. (I have edited the question to specify this) – rtheunissen Apr 14 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.
• If $k$ is constant, the amortized complexity is $O(\log n)$. – Yuval Filmus Apr 14 at 21:07