In Amortized Analysis, can we chose how big $n$ is?

Question

Suppose I want to show by contradiction that the amortized cost of a data structure with some operations cannot be less then $\Theta(k)$. I assume for the sake of contradiction that it is possible. Can I then choose an $n$, large enough, and a special sequence of operations and show that they take $\Theta(nk)$ and conclude that the amortized cost has to be at least $\Theta(k)$? Or does my counter example must be for any chosen size of $n$ sequences?

In other words, I want to show that for any large $n$ that satisfies $\frac{n}{2}>2^k-1$, the counter example works. Is this sufficient?

Edit: To show what I mean here is an example: I have a binary counter that supports the option INCREMENT and DECREMENT. It starts at all zeros at the start. I wanna show that the ammortized cost cannot be less than $\Theta(k)$.

So I assume the opposite. And I first do $2^k$ increment operations so that I have [1(k-1 zeros)] as the binary counter. Then I do $m$ DEC INC operations in succession where each of them will take $\Theta(k)$.

here we have $n=2^k+m$. Choosing $m=2^k$, we get $n=2^{k+1}$ so $m=\Theta(n)$. So we get total amount of work $\geq km=k\Theta(n)=\Theta(nk)$ so the amortized time is $\Omega(k)$.

However, the above argument only holds if $n\geq 2^{k+1}$, does this constitute a proof?

Answer 1

It depends a bit on what you mean with "choose an $n$". If you pick a fixed $n$, say a million, then no, that's not enough. Asymptotic notation already means "for sufficiently large inputs, the runtime is...". So a counterexample of any fixed size won't do.

If however you show a method that for an infinite number of sufficiently large $n$ produces a counterexample, then this is valid.