Calculation of T(n)

Question

Could someone explain to me how to calculate the T(n) of this algorithm being n >= 0? I’ve seen videos and classes and I can’t understand how this calculation works.

T(n) of an algorithm is how much of primitive operations it needs to do for a size input n.

int fib(int n){
    int ant, preant, atual, i;
    if(n>=2){
        ant = 1;
        preant = 1;
        for(i=n; i >=3; i--){
            atual = ant + preant;
            preant = ant;
            ant = atual;
        }
        return atual;
    } else {
        return n;
    }
}

Answer 1

This algorithm presented is very similar^{read observation at the end of the reply} an implementation of the algorithm to calculate the number n of the Fibonacci sequence, which in turn has linear temporal complexity (o(n)). So, you could say that the expected behavior of T(n) is a linear function, in the format T(n) = a*n + b, for general cases. However, there are special cases: any number with n <= 1 has T(n) = 2. How do I know this? Taking the table test. See how it went to n = 1:

1. checks position -1 >= 2 (n >= 2)
2. return position -1 value (return n)

I’m considering that the goto be part of the primitive comparison operation, something like jumpelse n >= 2, LABEL_ELSE

Now, what would it be like for another case? For a generic case of n? Let’s test with n = 4:

1. checks position -1 >= 2 (n >= 2)
2. assigns 1 to heading 0 (ant = 1)
3. assigns 1 to position 1 (preant = 1)
4. assigns position -1 value to position 3 (i = n)
5. check if position 3 >= 3 (i >= 3)
6. sum value of position 0 and value of position 1 (ant + preant)
7. gives result to position 2 (atual = ant + preant, and the sum has been considered above)
8. assigns position 1 to position 0 (preant = ant)
9. assigns the value of position 2 to position 1 (ant = preant)
10. decreases to position 3 (i--)
11. check position value 3 >= 3 (i >= 3)
12. sum value of position 0 and value of position 1 (ant + preant)
13. gives result to position 2 (atual = ant + preant, and the sum has been considered above)
14. assigns position 1 to position 0 (preant = ant)
15. assigns the value of position 2 to position 1 (ant = preant)
16. decreases to position 3 (i--)
17. check position value 3 >= 3 (i >= 3)
18. returns position 2 value (return atual)

So they gave 18 operations to n = 4. And to n = 5?

1. checks position -1 >= 2 (n >= 2)
2. assigns 1 to heading 0 (ant = 1)
3. assigns 1 to position 1 (preant = 1)
4. assigns position -1 value to position 3 (i = n)
5. check if position value 3 >= 0 (i >= 0)
6. sum value of position 0 and value of position 1 (ant + preant)
7. gives result to position 2 (atual = ant + preant, and the sum has been considered above)
8. assigns position 1 to position 0 (preant = ant)
9. assigns the value of position 2 to position 1 (ant = preant)
10. decreases to position 3 (i--)
11. checks position value 3 >= 0 (i >= 0)
12. sum value of position 0 and value of position 1 (ant + preant)
13. gives result to position 2 (atual = ant + preant, and the sum has been considered above)
14. assigns position 1 to position 0 (preant = ant)
15. assigns the value of position 2 to position 1 (ant = preant)
16. decreases to position 3 (i--)
17. checks position value 3 >= 0 (i >= 0)
18. sum value of position 0 and value of position 1 (ant + preant)
19. gives result to position 2 (atual = ant + preant, and the sum has been considered above)
20. assigns position 1 to position 0 (preant = ant)
21. assigns the value of position 2 to position 1 (ant = preant)
22. decreases to position 3 (i--)
23. checks position value 3 >= 0 (i >= 0)
24. returns position 2 value (return atual)

Twenty-four operations. From here, we were able to get the value of a in T(n) = a*n + b and then we’ll find out b:

T(5) = a*5 + b
T(4) = a*4 + b
T(5) = 24
T(4) = 18
T(5) - T(4) = a*5 + b - (a*4 + b) = a 
T(5) - T(4) = 24 - 18 = 6
a = 6
18 = a*4 + b = 6*4 + b = 24 + b
b = -6

So we have to, to n >= 2, T(n) = 6*n - 6. Therefore:

---

This algorithm, although very similar to a classical implementation to the algorithm that calculates the numbers in the Fibonacci sequence, contains an error that disqualifies it as such. See, for example, the portamento for n = 2:

1. checks position -1 >= 2 (n >= 2)
2. assigns 1 to heading 0 (ant = 1)
3. assigns 1 to position 1 (preant = 1)
4. assigns position -1 value to position 3 (i = n)
5. check if position 3 >= 3 (i >= 3)
6. returns position 2 value (return atual)

In not a moment position 2 (representing the variable atual) has been filled. This indicates that at this time the return of the function is undefined. This is prohibited in some programming languages, but the C compilers I know allow it. In many cases, the return will be a memory junk, any value, which can sometimes even match the appropriate value. At other times, some interpreters I’ve seen around initialize variables with 0. Also, see the output result for some numbers:

fib(0) => 0
fib(1) => 1
fib(2) => undefined
fib(3) => 2
fib(4) => 3
fib(5) => 5

There are some solutions to fix the algorithm:

• make 2 a special case and force return 1
• do preant = 0, ant = 1 and the loop until i >= 2

The first solution would add 1 extra step in special cases (and none in the general case, if the algorithm is well written); it would also change the composition of the function, being constant in the interval (-infty, 2] and linear in [3, +infty) (the original is constant in the range (-infty, 1] and linear in [2, +infty)).

The second solution does not change the number of steps in special cases, nor the intervals that define the behavior of the function, but would change the linear part; it would come out of 6*n - 6 for 6*n, since at least one loop (which in turn has 6 operations) will always be executed.

Answer 2

You can think inductively following the steps of your algorithm. To make the explanation simpler I will disregard the balance as a primitive instruction, I will only take into consideration the comparison, addition, subtraction and return, however the logic follows the same whatever operations I decide to consider (or disregard).

Let’s start with cases where n < 2, in the case T(0) e T(1):

So we have a comparison of n >= 2: we will consider 1 cost. The instruction is false then jumps to return n we will also cost 1. So it follows that T(n < 2) = 2, for these cases performs only two instructions.

Now we’re interested when we have an entrance n very big, because the bigger the n more times the loop will be executed and therefore more instructions.

First let’s consider the constant costs for an entry n very large:

1. comparison n >= 2

2. ant = 1

3. preant = 1

4. i = n is executed once to enter the loop

5. comparison i >= 3 will be done at least once to determine if you enter the loop

6. return atual will always be executed once

So we have 6 instructions that will always be executed for a n very large. Now we go to the instructions of the loop that will be executed according to the value of n:

1. ant + preant (considering the sum)

2. atual = ant + preant (we are only considering the assignment the sum has already been considered)

3. preant = ant

4. ant = atual

5. i--

6. i >= 3 the comparison will be executed every time it returns to the top of the loop

So we have 6 instructions that will be executed according to the size of the n. Now we must heed the instructions i = n and i >= 3 (stop), thus being the loop n-2 times. Therefore the recurrence of the algorithm is:

T(n) = 6 + 6(n - 2) 
T(n) = 6 + 6n - 12
T(n) = 6n - 6

You can do some test cases with small inputs to follow this method, also you can choose to consider the jump instructions or disregard the return instructions for example, in any case the method remains the same.