1
$\begingroup$

I'm trying to solve a problem from one of the older exams.

Question:

There's an infinite, one-dimensional board, with fields numbered consecutively $\ldots, -2, -1, 0, 1, 2, \ldots$ A move in the game consists of selecting a field and placing a token on it. If after placing the token it turns out that on two adjacent fields there are an equal number of tokens (at least one each), then we move all tokens from one of these fields to the other, clearing the first field and doubling the number of tokens on the second field. If there's a choice between two adjacent fields, we make that choice arbitrarily. Then we continue the described process of clearing the field and doubling the number of tokens on the adjacent field until there's not an equal number of tokens on two adjacent fields.

Example:

Suppose that on fields numbered $1, 2, 3, 4, 5$ there are $0, 1, 2, 4, 6$ tokens respectively. After adding one token to the field numbered $1$, we get the following arrangement of tokens on the board: $0, 0, 0, 8, 6$. A basic move in the game involves placing or removing a token. Therefore, moving $k$ tokens from one field to another requires performing $k$ removal operations and $k$ placement operations on the board. Analyze the amortized cost of a single move in the game measured by the number of basic moves.

I think first part of the solution goes like this: Suppose there are $n$ tokens on the board. No token could be moved more than $\log n$ times because with each move, it would be on a stack twice as large, and the height of that stack would be greater than the total number of tokens. For example, if there are $8$ tokens on the board, then no token could be moved 4 times because it would be on a stack of height $16$. Hence, each token could be moved at most $\log n = \log 8 = 3$ times. Therefore, the cost is at most $\log n$.

What is the method to establish a lower bound?

$\endgroup$

1 Answer 1

1
$\begingroup$

To prove a lower bound simply take a worst case example. We will prove the following:

Induction Hypothesis: There exists a sequence of moves that results in $n$ tokens at position $\log n$ that requires at least $n \log n$ place and remove operations. For simplicity, assume that $n$ is some power of $2$, and $\log$ with base $2$.

Base Case: Let $n = 2$. Then, place a token at position $1$ and $2$, each. Total place and remove operations are $4 > n \log n = 2$. Thus, the base case holds correctly.

Induction Case: Suppose there exits a sequence of moves that results in $n/2$ tokens at position $\log(n/2)$, which requires at least $(n/2) \log (n/2)$ operations.

Similarly, $n/2$ tokens can be obtained at position $\log(n/2)-1$ if the placement of tokens starts from index $0$. It also requires at least $(n/2) \log (n/2)$ operations.

Since the two sets are adjacent to each other, we move the tokens from position $\log n -1$ to position $\log n$. It requires $n$ remove and place operations.

Total operations are thus $\geq (n/2) \log (n/2) + (n/2) \log (n/2) + n = n \log n$. Hence, the induction hypothesis is holds.

$\endgroup$
3
  • $\begingroup$ So in the analysis of amortized cost, we consider the average cost but in the pessimistic case? I understand that such a pessimistic scenario exists, but I'm doubtful why we specifically consider it. Are we saying that in the worst case, the average cost of one operation is at least $\log n$? Thank you for your answer. $\endgroup$
    – Michał
    Commented Jan 7 at 14:40
  • $\begingroup$ @Michał yes, you understood it right. In the worst case, the average cost of one operation is at least $\log n$. And, the amortized cost itself means "average cost of an operation over $n$ iterations"; a operation could take more or less time in a particular iteration. $\endgroup$ Commented Jan 7 at 16:01
  • 1
    $\begingroup$ @Michał Note that there are examples, where amortized cost is $\Theta(1)$. However, we are looking for a lower bound, thus we had to consider a worst case example. $\endgroup$ Commented Jan 7 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.