Time complexity of recursion inside of for loop

Question

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.

Is this homework or some kind of assignment? Why do you think it is O(3^n)? — user9455968
– user9455968, Commented Apr 9, 2018 at 18:36
Impossible to answer without seeing control and find methods. — lexicore
– lexicore, Commented Apr 9, 2018 at 18:36
If you're doing a function that is O(n) 3 times, that's not 3^n - it's O(n) still. — Strikegently
– Strikegently, Commented Apr 9, 2018 at 18:38
I couldn't really find another working way to exit the method so I used exceptions. Which is probably very wrong and not what it's intended for. — Elif Sahin
– Elif Sahin, Commented Apr 9, 2018 at 18:42

Thiyagu · Accepted Answer · 2018-04-09 19:36:40Z

1

Here's my take on this

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

control method has a loop that runs for vertices number of times - So it is O(vertices).
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.

edited Apr 9, 2018 at 19:36

answered Apr 9, 2018 at 19:27

Thiyagu

18k5 gold badges49 silver badges88 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Elif Sahin Over a year ago

I've been thinking about this and I'm curious. Does the fact that the thrown exception is caught change its complexity? Or do exceptions stop it from going any further in any case and it's O(vertices^2) no matter what. Sorry, I had to ask.

Thiyagu Over a year ago

If you catch the exception and ignore (or not throw exception) the recursion continues for other values of r (2,3).

Elif Sahin Over a year ago

Ohh. My code catches the exception which I should've probably shown. Sorry.

Thiyagu Over a year ago

No. Having a catch outside find will not have any impact. It will still be O(vertices^2).

MD Ruhul Amin · Accepted Answer · 2018-04-09 19:42:20Z

0

       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).

edited Apr 9, 2018 at 19:42

answered Apr 9, 2018 at 19:03

MD Ruhul Amin

4,5022 gold badges24 silver badges38 bronze badges

6 Comments

Thiyagu Over a year ago

@lexicore What I told is partially correct, there is an exponential component as the recursive call happens in a loop

lexicore Over a year ago

@user7 I don't see why. find calls control at most 3 times and find recursively at most once. Won't that be vertices*(3*vertices) i.e. O(vertices^2)?

Thiyagu Over a year ago

@lexicore How are you saying find recurs at most once. Once it hit the base condition did you consider r=2,3 (assuming base condition won't throw an exception as in the OP ;))

Thiyagu Over a year ago

@lexicore So, I missed the throw Exception part. So you considered that? In that case find calls control at most 3 times is not right. As the loop runs at most once in each recursive call

lexicore Over a year ago

@user7 You are right. I was wrong. If graph[n][i] is always 0, it will recur 3x.

|

Collectives™ on Stack Overflow

Time complexity of recursion inside of for loop

2 Answers 2

4 Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related