CODEWITHSUNDEEP
algorithmtime-complexity
Pierre P.
Pierre P.

Reputation: 1065

Running time of this algorithm

I have this algorithm and I can't figure out what is its time complexity. 

int oc(int n) {
    if (n == 0)
    {
        return 0;
    }
    int s = p[n][0];
    for (int i = n-1; i > 0; i--)
    {
        int a = p[n][i] + oc(i);
        if (s > a)
        {
            s = a;

        }
    }
    return s;
}

I assume there is (n-1) iterations on the for-loop but can figure out what is total running time when using the recursion.

Upvotes: 1

Views: 67

Answers (2)

simon
simon

Reputation: 1405

Let T(n) is a complexity of computing oc(n). Since for computing oc(n) you are running for loop from n-1 to 1 and recursively calling oc(i), hence

T(n)=T(n-1)+T(n-2)+...+T(1) (*).

If instead of T(n-1) we put

T(n-1)=T(n-2)+T(n-3)+...+T(1)

in (*) equality we will get:

T(n)=2*(T(n-2)+...+T(1))

If we continue same iteration for T(n-2), T(n-3) etc. we will conclude tô following equality:

T(n)=2*(T(n-2)+...+T(1))
=4*(T(n-3)+...+T(1))
=2^i*(T(n-i-1)+...+T(1))
=2^n*T(1)/2=O(2^n).

The reason of this complexity is - your algorithm calculating same thing for many times. If you memorize values in array for which you have calculated the value of oc function and add a check in the first part of function which will return the value directly from array (in case it is already calculated) instead of running loop and again doing same job, the complexity of you algorithm will dramatically change and will be O(n), since the algorithm will calculate all values and store when doing first iteration of your loops.

Upvotes: 1

trincot
trincot

Reputation: 349956

It is O(2n). See how the number of iterations builds up for increasing n:

 n | f(n) = total iterations
---+-------------------------------------------------
 1 | 0
 2 | 1 + f(1) = 1 + 0 = 1
 3 | 2 + f(2) + f(1) = 1 + 2f(2) = 1 + 2.1 = 3
 4 | 3 + f(3) + f(2) + f(1) = 1 + 2f(3) = 1 + 2.3 = 7
...| ...
 n |  .... 1 + 2.f(n-1) = 2^(n-1) - 1

Upvotes: 0

Related Questions