# Frogs Game Amortized Analysis

The game is defined by two integer parameters: n and k. We are given an array of n sets: $$S_1, S_2, ...., S_n$$ such that, each of them is a subset of $$\{1, 2, ..., k\}$$. Adversary picks a set $$S_i$$ in each turn and changes it into an empty set. the cost that we must paid is a minimal number $$t$$ such that: $$S_i \subseteq S_{i-t} \cup S_{i-t+2} \cup ... \cup S_{i-1}$$ or $$S_i \subseteq S_{i+1} \cup S_{i+2} \cup ... \cup S_{i+t}$$ if there is no such $$t$$ we must pay: $$min(i, n-i)$$ can we settle an upper bound on the amortized cost of $$n-1$$ turns?

• Do you want a bound that holds for all possible arrays, and depends on only $n$ and $k$? What regime of $k,n$ are you interested in? Where $k$ is very small compared to $n$? Where $k$ is comparable to $n$? If there is no $t$ such that either equation holds, then am I correct to assume that the cost is $+\infty$? What's the motivation for this question or the context where it arises? What have you tried? What is the best bound you have been able to find so far?
– D.W.
Jun 22 at 20:07
• when there is not such $t$, we must paid $min(i, n-i)$. I interest in cases that $k = o(log n)$. Jun 23 at 7:35
• I'm motivated to this problem because it is very helpfull tool for online algorithm analysis. I fact I want to solve this problem to settle an upper bound on competitive ratio on an online algorithm for chordal graphs coloring. Jun 23 at 7:42
• Your question does not match your comment. $\min(i,n-i)$ or $\min(n,n-i)$? Please edit the question accordingly.
– D.W.
Jun 23 at 17:22
• The quantifiers are not clear at all. An adversary gives the array of sets, and also the adversary picks the $i$ in each round, i.e., we have no choice anywhere in this game? Jun 24 at 7:31