Recursive algorithm. Time complexity

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 999 Views - Last Post: 09 April 2017 - 12:56 PM

#1 Daniel551  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 09-April 17

Recursive algorithm. Time complexity

Posted 09 April 2017 - 03:16 AM

I need your help with time complexity:

I have this system of equation, and I had to do the same thing using recursion in C#, so I came up with this :


 public static long F1(int n)
        {
            if (n > 1) return F1(n - 2) + 10 * (long)Math.Pow(F1(n/6),2) + 6 * F1(n / 7) + ((long)Math.Pow(n,4) / 5);
            else return 2;
        }


I need help calculating the time complexity of this algorithm, and I don't even know where to start and how to do it, could you please give me a hand?

Thank you for any kind of help.

Is This A Good Question/Topic? 0
  • +

Replies To: Recursive algorithm. Time complexity

#2 andrewsw  Icon User is online

  • say what now
  • member icon

Reputation: 6409
  • View blog
  • Posts: 25,903
  • Joined: 12-December 12

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 05:34 AM

What have you studied and understand about time complexity?
Was This Post Helpful? 0
  • +
  • -

#3 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 5924
  • View blog
  • Posts: 20,255
  • Joined: 05-May 12

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 05:36 AM

You would start by counting the number of operations performed. This is no different from how you would do things for a standard procedural function.
Was This Post Helpful? 0
  • +
  • -

#4 Daniel551  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 09-April 17

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 05:48 AM

I'm just starting to study algorithm analysis and I don't know much. I assume, however, that the complexity grows exponentially since I have an example of Fibonacci sequence that runs in exponential time and my recursion looks quite similar but still much more complex.
Was This Post Helpful? 0
  • +
  • -

#5 jon.kiparsky  Icon User is offline

  • Chinga la migra
  • member icon


Reputation: 10721
  • View blog
  • Posts: 18,354
  • Joined: 19-March 11

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 08:23 AM

Fill in the table:

N | # of calls to F1
--------------------
0 |
1 |
2 |
3 |
4 |


See if you see a pattern developing
Was This Post Helpful? 0
  • +
  • -

#6 Daniel551  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 09-April 17

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 08:40 AM

N | # of calls to F1
--------------------
0 | 1
1 | 1
2 | 4
3 | 4
4 | 7


Is this correct?

I calculated using this:

 public static long F1(int n)
        {
            Console.WriteLine("a");
            if (n > 1) return F1(n - 2) + 10 * (long)Math.Pow(F1(n/6),2) + 6 * F1(n / 7) + ((long)Math.Pow(n,4) / 5);
            else return 2;
        }


And then just added all the "a".
Was This Post Helpful? 0
  • +
  • -

#7 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 5924
  • View blog
  • Posts: 20,255
  • Joined: 05-May 12

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 08:59 AM

Yes. That will give you a first pass at the analysis. Next try to find a function that tightly defines the upper bound for those counts of "a". Once you have that function, find the "most significant term" of that function. Simplify that term and that is the big O.
Was This Post Helpful? 0
  • +
  • -

#8 Daniel551  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 09-April 17

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 09:14 AM

Alright, I feel kind of lost now. Originally I thought the time complexity is going to be O(3^n), because each time this function is called 3 more functions are being called too. ( Basically the same principle as for Fibonacci sequence )
public static int Fibonacci(int n)
        {
            if (n <= 1)
                return n;
            else
                return Fibonacci(n - 1) + Fibonacci(n - 2);
        }


The Big-O for this is O(2^n).

But having that table of N and # of calls shows that for example, 3^4 is nowhere near to 7. What's going on here? :/
Was This Post Helpful? 0
  • +
  • -

#9 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 5924
  • View blog
  • Posts: 20,255
  • Joined: 05-May 12

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 10:16 AM

You need to look at the general case for all inputs. Also, the bounding function can be above the actual values, but it should follow the same "shape" as the actual values.
Was This Post Helpful? 0
  • +
  • -

#10 Daniel551  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 09-April 17

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 10:29 AM

So my assumption of O(3^n) is correct?
Was This Post Helpful? 0
  • +
  • -

#11 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 5924
  • View blog
  • Posts: 20,255
  • Joined: 05-May 12

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 10:38 AM

How did you arrive at the assumption?
Was This Post Helpful? 0
  • +
  • -

#12 jon.kiparsky  Icon User is offline

  • Chinga la migra
  • member icon


Reputation: 10721
  • View blog
  • Posts: 18,354
  • Joined: 19-March 11

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 10:44 AM

Your assumption is incorrect, because it is an assumption the problem is not about assumptions. The problem is about coming to a justifiable conclusion - therefore, the justification for that conclusion is as important as the conclusion itself.

I'm not saying anything here about the actual time complexity of this function, of course. I'm just saying that ANY answer which consists of an assumption is incomplete until that assumption is justified.
Was This Post Helpful? 0
  • +
  • -

#13 Daniel551  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 09-April 17

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 10:51 AM

Used this as a reference. (It's about Fibonacci sequence and the code for that is a few posts above )

Reference

And because in each step I call my function 3 times that should make it O(3^n).
Was This Post Helpful? 0
  • +
  • -

#14 Daniel551  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 09-April 17

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 11:20 AM

View Postjon.kiparsky, on 09 April 2017 - 10:44 AM, said:

Your assumption is incorrect, because it is an assumption the problem is not about assumptions. The problem is about coming to a justifiable conclusion - therefore, the justification for that conclusion is as important as the conclusion itself.

I'm not saying anything here about the actual time complexity of this function, of course. I'm just saying that ANY answer which consists of an assumption is incomplete until that assumption is justified.



These are very good words. And I do understand that. However, calculating time complexity is a fairly new thing to me and I don't know much. I spend a lot of hours searching online for examples and then I try to use something of it on my problem. As I posted before, I've used an example of solving Big-O for the Fibonacci sequence, and I've tried to use the same principle here.
Was This Post Helpful? 0
  • +
  • -

#15 jon.kiparsky  Icon User is offline

  • Chinga la migra
  • member icon


Reputation: 10721
  • View blog
  • Posts: 18,354
  • Joined: 19-March 11

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 11:39 AM

Okay, so let's suppose that your assumption is true. What would that mean?

One thing that it would mean, roughly speaking, is that the curve 3^n is an upper bound for the number of recursive calls made by this function. So if you can prove that is the case, then you would have established that 3^n is an upper bound for this function. This wouldn't prove that 3^n is the tightest bound for this function, of course, but it would show that this function is bounded above by that curve. So how would you prove that?

Hint: Consider that this is a recursive function, and there is a mathematical proof structure that is very well suited to proofs on recursive functions.
Second hint: As always, it will be useful to start with a clear statement of what it is you're trying to prove.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2