0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Do you want to use induction? $\endgroup$ – rus9384 Sep 12 '17 at 9:38
  • $\begingroup$ @rus9384 What do you mean? $\endgroup$ – AspiringMat Sep 12 '17 at 9:46
  • $\begingroup$ You can show that it requires $\omega(n-\varepsilon)$ operations. But not $\Omega(n)$. Speaking of your method, of course. $\endgroup$ – rus9384 Sep 12 '17 at 9:59
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, that's what I meant. What I mean is for any $n$ such that $\frac{n}{2}> 2^k-1$, my counter example would work. However, for any $\frac{n}{2}\leq 2^k-1$, it would fail. Is this sufficient? $\endgroup$ – AspiringMat Sep 12 '17 at 9:38

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.