CODEWITHSUNDEEP
javatime-complexitybig-ocomplexity-theory
Elif Sahin
Elif Sahin

Reputation: 75

Time complexity of recursion inside of for loop

Can you help me with the time complexity of this bit of code. I think it's 3^n but I'm a newbie so I'm probably wrong.

public void find(int n) throws Exception
    {
        if (n == vertices){
            throw new Exception("Solution found");
        }

        for (int r = 1; r <= 3; r++)
        {
            if (control(n, r))
            {

                color[n] = r;
                find(n + 1);

                color[n] = 0;
            }
        }    
    }

    public boolean control(int n, int r)
    {
        for (int i = 0; i < vertices; i++){
            if (graph[n][i] == 1 && r == color[i]){
                return false;
            }
        }
        return true;
    }

Any help is appreciated!

Edit: I guess I misunderstood some things and the complexity is n.

Upvotes: 0

Views: 827

Answers (2)

MD Ruhul Amin
MD Ruhul Amin

Reputation: 4502

       n
      /|\
     / | \ 
    /  |  \
   /   |   \
(n+1) (n+1)(n+1) --> control(vertex)-> O(Vertex)
 /|\
/ | \ . . . .   . .

So it seems there are total, 3^1+ 3^2+...+3^vertex nodes and on each node you are doing O(n) operation on each node. So the complexity is O((3^1+ 3^2+...+3^n) * n) = O((1-3^n)/2)*n) eventually O((3^vertices)*vertices).

Upvotes: 0

Thiyagu
Thiyagu

Reputation: 17880

Here's my take on this

EDIT: This applies when the base condition does not throw an exception

  1. control method has a loop that runs for vertices number of times - So it is O(vertices).

  2. find is a recursive function that stops when n reaches vertices. (Assuming n starts from 1) It calls control for n=1,2,3... vertices.

find is called from a loop for 3 times. Each recursive calls involves this and hence this makes it exponential - O(3^vertices).

So, finally, it is O(3^vertices) * O(vertices) which is O(3^vertices)

EDIT:

Since you have throw new Exception("Solution found");, it will blow up once n reaches vertices. So it is O(vertices^2) in that way.

Upvotes: 1

Related Questions