# Is the complexity of this algorithm O($\sqrt{n}$) or linear?

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?

• What is $n$? Is it equal to the height you wish to find? Jan 17, 2019 at 14:45
• n is the number of steps on the staircase, so indirectly height, yes.
– V S
Jan 17, 2019 at 14:46
• 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. Jan 17, 2019 at 14:48

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})$$.