HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Complexity of many constant time steps with occasional logarithmic steps

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
constantwithlogarithmictimecomplexitymanyoccasionalsteps

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#106957, answer score: 8

Revisions (0)

No revisions yet.