(A) When Shankar chooses a number between 1 and n, Geeta should start guessing √n, 2√n, 3√n, 4√n, and so on. The first time her guess exceeds Shankar's number, the range of numbers has been narrowed down to √n numbers; she then starts guessing sequentially in that range.
(B) If Shankar guesses an arbitrarily large number n, then Geeta may guess 1, 4, 9, 16, 25, and so on, to discover k such that Shankar's number lies between k2 and (k+1)2. Then guess k2+1, k2+2, k2+3 and so on. On the whole, this requires O(√n) steps.