Worst time complexity (Big O) for 1 for loop

Question

So I understand most complexity problems; however, this puzzles me.

When the second statement in the for loop is as below (i * i < n), what would tre Big O for the loop be? How would it be calculated?

for ( i = 1 ; i * i < n ; i++)

Answer 1

i*i<n

can be transformed as

i<sqrt(n)

So its acutally O(sqrt(n))

Answer 2

Assuming that n is a proxy for the size of the input (and that your code will only execute the loop body once for each processable member of the input, and there is no other input element selector logic).

i * i < n
  i^2 < n
    i < Sqrt(n)

So, a time complexity of O( Floor( Sqrt( n ) ) ).

Let's see an example with n = 10 (the table shows the state of the variables at the end of each iteration, at the moment exactly before i++ is evaluated and the i * i < n test is performed).

Iteration,   i,   i * i,  n
        1,   1,       1, 10
        2,   2,       4, 10
        3,   3,       9, 10
        4,   4,      16, 10 -- 16 > 10, abort loop
        5,   5,      25, 10 -- for illustrative purposes

(Note that as the i^2 < 10 check is performed before the loop is executed, iteration 4 will not be executed, so the loop will be executed 3 times. The exact square-root of 10 is 3.1622... but iteration-counts are 0-based natural numbers, so use Floor.).