what is the right time complexity of this function

user_3932543 0
Viewed 171

I'm a beginner in data structure and algorithms. I have come across this problem in a book (Data Structures And Algorithms Made Easy In Java) and the complexity is given as O(√n) in the book. To my understanding, it looks the function grows more than O(√n) but less than O(n) with the input.

public void function (int n) {
   int i=1, s=1;
   // s is increasing not at rate 1 but i
   while( s <= n) {
      i++;
      s= s+i;
      System.out.println(“*");
   }
}

Can you please explain what is the correct time complexity of this function?

big-o complexity-theory time-complexity algorithm
1 Answers

The book is correct. Each time, one is added to i and i is added to s. Hence, s will be 1 and 1 + 2, 1 + 2‌ + 3, ..., 1 + 2 + 3 + ... + k. Now, k is the number of running loop and the complexity is Theta(k) or O(k). Now to find the value of k, we need to solve 1 + 2 + ... + k = n. As 1 + 2 + ... + k = k(k+1)/2, we will have k*(k+1)/2 = n. Hence, k = Theta(sqrt(n)) (just solve the equation), and it means the algorithm is in O(sqrt(n)).

user_37688710
Related