CODEWITHSUNDEEP
c++
nains
nains

Reputation: 259

How would I calculate the runtime of this function?

I have this function written in C++ and I am trying to calculate the runtime of it. I believe the runtime is O(n^2) (I attempt to explain why using comments in the code), but I was looking for confirmation.

    void f1(int n)
    {
    int t = sqrt(n);
      for(int i = 0; i < n; i++){              //this outer for loop by itself has a runtime of O(n) but decreases by sqrt(n) every time it goes back to the top
        for(int j = 0; j < n; j++){          //this inner for loop has a run time of O(n) but decreases by sqrt(n) every time it goes back to the top of the function
            // do something O(1)
        }
        n -= t;                             
      }
    }

Upvotes: 2

Views: 81

Answers (1)

Dima Chubarov
Dima Chubarov

Reputation: 17159

Let's assume this is sqrt() from cmath header. The function returns a double precision value t such that round(t * t) == n.

Let's estimate the number of operations:

  • On the first iteration of the outer loop the inner loop performs n iterations.

  • On the second iteration of the outer loop the inner loop performs n - t iterations,

  • and so on...

The number of iterations of the outer loop would be between t and t + 1 as t * t might be less than n.

So to calculate the total number of iterations of the inner loop we have to calculate the following summation:

n + (n - t) + (n - 2*t) + ... + (n - t * t) = 
n * t - t * (1 + 2 + ... + t) = 
n * t - t * t * (t + 1) / 2 = 
t * t * t - t * t * (t + 1) / 2 =
t^3/2 - t^2/2  = O(n^(3/2))

Upvotes: 2

Related Questions