Time complexity for recurrence of a number

Question

   public static void fun3(int i)
    {
        if(i<10)
        {
            fun3(i+1);
            fun3(i+2);
            System.out.println(i);
        }
    }

Recurrence for this code is: T(n)=T(n+1)+T(n+2)+O(9) the problematic thing is if condition here if(i<10). Where i can grow to infinity towards the negative side (e.g -1000, or -287131287238238 etc). I need its time complexity using recurrence tree. How to calculate height of the tree??

O(n) is estimated for n approaching infinity. In your case there is an upper bound of 10 (or any other final number), that is no matter how large n becomes you will have the same cost. This leads to O(1) — Oleg Sklyar, May 14 '18 at 09:32
@OlegSklyar it should be O(n) if i=n and it will execute till n+9. i dont know how to calculate height of recurrence tree. — GPU.., May 14 '18 at 09:36
@Shubham why people edit just because something should be in code block what about numbers -1000 and -287131287238238 are these a code? i need an answer to this.. — GPU.., May 14 '18 at 09:41
See the answer below: the way your question is formulated it is O(1), actually no matter how high is the number as long as it is final, anything else is insider knowledge that you may possess and we do not — Oleg Sklyar, May 14 '18 at 09:41
@GPU.. You want to believe your own truth. No probs, but what is then the reason for asking the community? Until the value for 10 becomes an argument to your method and can grow arbitrary the complexity is O(1). You want a different answer, make 10 to n, add it as an argument and then you may get one. — Oleg Sklyar, May 14 '18 at 09:52
@OlegSklyar can you make recurrence tree and can you tell me how to calculate tree height for this? Well! this requirement is written in the question. — GPU.., May 14 '18 at 09:54
The depth is roughly n - i, where n=10, but it would be obvious if you just cared to try this on paper (works also for negative i). The example is also quite bad as it will compute the same paths many times — Oleg Sklyar, May 14 '18 at 10:01

score 1 · Answer 1 · answered May 14 '18 at 09:22

1

Since you have no calls for i>=10, and for all i=0 .. 9 there are finite number of calls you have an upper bound for the total number of calls for all i.

Therefore the answer is O(1).
The constant factor is the maximum of calls for the values i=0...9. The code indicates that the most calls are made for i=0 (or if 0 is not allowed, i=1)

answered May 14 '18 at 09:22

MrSmith42

9,961
6
38
49

or it may go -one million – GPU.. May 14 '18 at 09:23
9

You should mention this in your question, because complexity is in general analysed for the case that the argument grows. So the behavior for i -> infinity. – MrSmith42 May 14 '18 at 09:26

score 1 · Accepted Answer · answered May 18 '18 at 05:21

The height of the tree is abs(10 - i) for i < 10 and 0 for i >=10 (abs indicates absolute value). At each level you have twice more branches than the level before. When you sum them up you will end up with a time complexity of O(2^abs(10-i)) or O(2^abs(i)) for i < 10 and O(1) for i>=10. The analysis is similar to fibonacci sequence for which you can find many reference like this.

Time complexity for recurrence of a number

2 Answers2