 Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki Blog Search Turing Chat Room Members
Time complexity of recursive algorithm graph       Author Message
garywoot Posted: Tue Dec 10, 2013 2:30 am   Post subject: Time complexity of recursive algorithm graph 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 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  Posted: Tue Dec 10, 2013 2:45 am   Post subject: 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. Tony's programming blog. DWITE - a programming contest. garywoot Posted: Tue Dec 10, 2013 3:14 am   Post subject: Re: RE:Time complexity of recursive algorithm graph

Tony @ Tue Dec 10, 2013 2:45 am wrote:
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  Posted: Tue Dec 10, 2013 12:24 pm   Post subject: 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. Tony's programming blog. DWITE - a programming contest. Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First        Page 1 of 1  [ 4 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: