CODEWITHSUNDEEP
javatime-complexity
TheAptKid
TheAptKid

Reputation: 1571

Time complexity of the following method

I'm trying to determine the time complexity of the following method. At the beginning I have three for loops which would yield m^3. I don't know how to determine, what is the time complexity of the recursive call at the end of the method.

Can someone help me with this?

void p(int n, int m) {
    int i,j,k ;
    if (n > 0) {
        for (i=0 ; i < m ; i++)
            for (j=0 ; j < m ; j++)
                for (k=0 ; k < m ; k++)
                    System.out.println(i+j*k) ;  
        p(n/m, m) ;
    }
 }

Upvotes: 0

Views: 137

Answers (2)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Followinyg the steps below would allow you to deduce the time complexity in formal manner:

enter image description here

Upvotes: 0

V-X
V-X

Reputation: 3029

O(m^3) is execution without aditional recusion, as you mentioned.

The total time is just multiply of time this single step.

For n = m^(k-1) is the step executed k times, thus it has O(k*m^3), which is O(ln(n)*m^3).

Upvotes: 2

Related Questions