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