1
$\begingroup$

Let's say I have two identical jars and I want to find the height that the jars will breaks when dropped from various heights. I can drop the jars from height increments using steps on a staircase. I want to solve this problem sublinearly.

I decided to increment using square numbers (1, 4, 9, 16..etc) for a complexity of O($\sqrt{n}$), where n is the number of steps on the stairs, so I know that I have an upper and lower bound once the first jar breaks. If the jar breaks at 16, I know that the height that it breaks at is between 9 + 1 and 16. If I were to run the algorithm linearly (on the second jar) from 10 to 16, would this make my algorithm linear?

$\endgroup$
  • $\begingroup$ What is $n$? Is it equal to the height you wish to find? $\endgroup$ – dkaeae Jan 17 at 14:45
  • $\begingroup$ n is the number of steps on the staircase, so indirectly height, yes. $\endgroup$ – Shawn S Jan 17 at 14:46
  • $\begingroup$ Can you compute with a variable, which is $n$ here? Can you compute how many drops will be used? For simplicity, you could assume $\sqrt n$ is an integer at first, just to see what happens. $\endgroup$ – Apass.Jack Jan 17 at 14:48
1
$\begingroup$

No, it would not make the algorithm linear. The worst-case scenario would be $n = m^2 + 1$, where $m$ is some positive integer. In this case, you have an additional $(m+1)^2 - m^2 = 2m + 1$ many tries (since the next square after $m^2$ is $(m+1)^2$ and $n < (m+1)^2$), which is roughly equal to $2\sqrt{n} \in \Theta(\sqrt{n})$.

$\endgroup$

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.