----------------------------------- garywoot Tue Dec 10, 2013 2:30 am Time complexity of recursive algorithm graph ----------------------------------- http://puu.sh/5I2s0.png I know the first 2 for loops is O(n^2), and then the third for loop is O(2m), then we have the if statement for the recursive part. So would it be f(n) = n^2 + 2m * f(n-1)? I omitted constant time obviously. So I'm guessing base case is f(1) = k. But the answer is O(n^3). I have no idea what i'm doing... any help? Also, similar question http://puu.sh/5I2tu.png So it should be f(n)= 2m * 2mn * f(n-1), and f(1) =k (no idea what I'm doing... i'm just guessing here). The answer is O(m^2*n) any help within 8 hours would be appreciated ----------------------------------- Tony Tue Dec 10, 2013 2:45 am RE:Time complexity of recursive algorithm graph ----------------------------------- You need to actually solve for the value of f(n-1). But you already know what it is! If f(n) = n^2 + 2m * f(n-1) then f(n-1) = (n-1)^2 + 2m * f(n-2) which you can put back into the original equation. f(n) = n^2 + 2m * ((n-1)^2 + 2m * f(n-2)) etc. Keep going until you remove f() from the right side of the equation, then simplify. ----------------------------------- garywoot Tue Dec 10, 2013 3:14 am Re: RE:Time complexity of recursive algorithm graph ----------------------------------- You need to actually solve for the value of f(n-1). But you already know what it is! If f(n) = n^2 + 2m * f(n-1) then f(n-1) = (n-1)^2 + 2m * f(n-2) which you can put back into the original equation. f(n) = n^2 + 2m * ((n-1)^2 + 2m * f(n-2)) etc. Keep going until you remove f() from the right side of the equation, then simplify. not sure how to "keep going and simplify". The third equation would be: f(n) = n^2+2m[(n-1)^2+2m(n-1)^2+4m^2f(n-3)], .... what exactly would be the i'th case? I don't see a pattern here.. and why is this equation so tedious? Is this the right way to do a multiple choice question worth 1 mark on a 100 mark 3 hour final exam? Because I would probably get 0% on the final then haha ----------------------------------- Tony Tue Dec 10, 2013 12:24 pm RE:Time complexity of recursive algorithm graph ----------------------------------- I'm sure that you've had assignments and a lecture dedicated to doing just this. With practice, it gets easier. You know that this recursion can only be N levels deep. f(n-2), f(n-3), ..., f(n-n), at which point it terminates with a constant.