Complexity of Recursion inside for loop

Question

I'm trying to analysis the complexity of this algorithm, I predicted that it's t(n) = n*t(n) + 1 and solve the t(n) via master theorem which is n^logn. however, I'm not sure, and stuck with it.

  Algorithm CheckPath(m[0..n-1][0..n-1],v1,v2)
       if v1==v2
       return 0
   cost = 0
   for i = 0 to n-1
     if  m[v1]m[v2]!=0 //any path exits
       cost2 = m[v1]m[v2]+checkpath(m,i,v2)
       if cost2<cost OR cost==0
         cost = cost2
return cost

EDIT: I corrected the costtmp as cost 2, it does not goes to an infinite loop while I check if v1==v2 return 0

n*t(n) + 1 is undefined (the recursive formula stays at n) , probably meant n*t(n-1), which is more O(n!) — amit
– amit, Commented Dec 3, 2013 at 11:29

yasen · Accepted Answer · 2013-12-03 11:33:20Z

2

I think your approach is wrong. You have an algorithm, which runs over some graph. So try to find its complexity over the underlying graph and not over the recursion you run.

But to answer your original question, your recursion has exponential complexity (and probably it does not terminate), unless your graph is a DAG (directed acyclic graph). The reason for that is because you don't mark the already reached vertices as such. Therefore, the recursion can infinitely loop between two vertices u and v, such that the edges (u, v) and (v, u) are in E (or simply if your graph is unoriented, then any edge will cause this).

answered Dec 3, 2013 at 11:33

yasen

1,2607 silver badges13 bronze badges

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

Comments

chill · Accepted Answer · 2013-12-03 11:53:42Z

0

For me it seems like:

t(n)   = 1 + t(1) + t(2) + ... + t(n-3) + t(n-2) + t(n-1) 
t(n-1) = 1 + t(1) + t(2) + ... + t(n-3) + t(n-2)
t(n-2) = 1 + t(1) + t(2) + ... + t(n-3)
...
t(4) = 1 + t(1) + t(2) + t(3) = 8
t(3) = 1 + t(1) + t(2) = 4
t(2) = 1 + t(1) = 2
t(1) = 1

Looking at the first few members of the sequence, it looks like the closed form is t(n) = 2^(n-1).

Can we prove this by induction?

For n == 1 we have t(1) = 2^(1-1) = 1 Suppose we have t(k) = 2^(k-1) for each k < n. Then:

t(n) = 1 + t(1) + t(2) + ... + t(n-1) = 1 + 2^0 + 2 + 4 + ... + 2^(n-2) = 2^(n-1)

Hence, T(n) = O(2^n)

answered Dec 3, 2013 at 11:53

chill

17k2 gold badges42 silver badges49 bronze badges

Collectives™ on Stack Overflow

Complexity of Recursion inside for loop

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related