Tag Info

11

What is meant by "lower bound" in this case is a lower bound on the worst-case number of comparisons. In this case, it happens to also be an upper bound. The lower bound has to be something that is true for every possible N and every possible combination of elements in both arrays, right? 2*N* - 1 seems more like it would be the upper bound since there is ...

6

The authors meant "show that any algorithm makes at least $2N-1$ comparisons in the worst case". See Toms answer and comments for an explanation.

2

In my opinion the problem statement seems poorly posed. It's not clear what is meant by the problem statement. Normally, if we write $a$ or $b$ the assumption is that they are a constant: they do not depend on $n$. If they are intended to be a function of $n$, then they should be written as $a(n)$ or $b(n)$. Since that wasn't done, the only assumption I ...

1

Your problem amounts to solving $2^{128} c - a^y z = 1$. I assume you are given $a,y$ and must find $c,z$ that satisfy the equation. I suggest you first solve $$a^y z \equiv 1 \pmod{2^{128}}.$$ This has as solution $$z \equiv (a^{-1})^y \pmod{2^{128}},$$ so you can find a solution for $z$ by computing the inverse of $a$ modulo $2^{128}$ (using one ...

Only top voted, non community-wiki answers of a minimum length are eligible