Q:

Two egg dropping puzzle variation: unknown/infinite floors

Preface 
This problem was inspired by a similar question last week on SO, that got deleted before it was clear what the real question was. I think this variation makes a nice problem that I wanted to share.
Two Egg Problem
A detailed definition and solution can be found here, but I will add a quick summary:
Definition

You are given two eggs, and access to a k-storey building. Both eggs
  are identical. The aim is to find out the highest floor f* from which an
  egg will not break when dropped out of a window from that floor. If an
  egg is dropped and does not break, it is undamaged and can be dropped
  again. However, once an egg is broken, that’s it for that egg. What is the fastes (least amount of drops) way to find f*?

Solution
The idea is to drop the first egg from floors sqrt(k), 2*sqrt(k), 3*sqrt(k)... k. If the egg breaks at floor i*sqrt(k) use the second egg to test the remaining floors between (i-1)*sqrt(k) and i*sqrt(k)-1. Overall this will result in at most 2*sqrt(k) drops so the complexity will be O(sqrt(k)).
Just for completeness: there is a method with less drops in the worst-case (details can be found here), which however has the same complexity of O(sqrt(k))
The Question: Two Egg Problem with infinite/unknown floors
Now imagine that you have no information about the number of floors k or k is infinite. Is it possible to find f* more efficient than just testing each floor in O(f*)? 
In other words: Is there an efficient method to drop the two eggs whose runtime complexity is independent from k but only depends on the answer f*?

A:

There is a simple method that has O(sqrt(f*)) complexity. Make your nth step to be n floors up, that is, check floors 1, 3 (1 + 2), 6 (1 + 2 + 3), etc. This way at the nth step you will be on n*(n+1)/2 floor, and you will reach f* in n = O(sqrt(f*)) steps. 
Then for the second egg you will need to go n single steps over your last step in stage 1, which will add another O(sqrt(f*)).
If O(sqrt(k)) was optimal for known k, this method has to be optimal in terms of complexity, too.

