posted 7 years ago
Hi Tonks,
In the second case, you perform g(0), g(1), g(2), ..., g(N). If g performs in linear time, then the loop will take 0 + 1 + 2 + ... + N to complete, or (N^2)/2. The division by 2 has no bearing on the complexity. The complexity class only considers the degree of the polynomial, in this case N^2.
The third case has a wrong answer. The answer is O(N*k), or O(N) if k remains constant. Since k is a constant, the method call will always perform in constant time.