Question 8-1

[5 pts] Suppose we were to execute f(n) for some number n using the following method.

public class Question1 {
  public static void f(int n) {
    int i = 1;
    while(i * i <= n) {
      i += 1;
    }
    IO.print(i - 1);
  }
}

In terms of n, how much time does this method take? Use Big-O notation to express your answer, and provide the tightest bound that you can.

Solution

O(sqrt(n)) (or O(n^1/2))