polynomial time complexity

There's this code from here

ub4 additive(char *key, ub4 len, ub4 prime)
{
  ub4 hash, i;
  for (hash=len, i=0; i<len; ++i) 
    hash += key[i];
  return (hash % prime);
}

They say this takes 5n+3 instructions. How did they calculate it? How should i calcul开发者_JAVA技巧ate it?

---

To make this calculation You need some base primitive system. For instance in The art of Computer programming, Knuth uses the MIX computer to do these kind of calculations. Different base computers might have different instructions, and different outcomes to this kind of calculation. In your particular example a common way to set it up would be:

• hash <- len (1 op)
• i <- 0 (1 op)
• i < len, i++ (2*n ops)
• key[i] lookup (n ops)
• hash + key[i] (n ops)
• hash <- hash + key (n ops)
• hash % prime (1 op)

and this would sum up as 5n + 3.

Variations might be along the lines of:

• declaring/creating the two hash and i, might be time consuming. A normal cpu might not need to do extra work because of the declarations, think register/stack storage.
• the hash += hash + key[i] might be counted as one operation on the base system, and so on.

Edit: Note that these kind of calculations are mostly useful as thought experiments on hypothetical hardware. A real life processor would quite likely not behave exactly as these calculations other than in very rare cases.

---

On the inside of your loop, you have 5 operations that run each iteration:

1. compare i<len
2. get index key[i]
3. adding hash + key[i]
4. assign into hash
5. increment ++i

Your loop runs n times, thus 5n

Outside of the loop, you have 3 operations:

1. assign len into hash hash=len
2. assign 0 into i i=0
3. perform hash % prime

Thus, 5n + 3.

---

Let's start counting the instructions.

1. hash=len and i=0 execute once, no matter what, so we have at least 2 instructions.
2. hash % prime and return execute at least once, so this is either 1 or 2 instructions (depending on whether or not you count "return" as an instruction... I suspect they do not).
3. Each iteration of the loop requires i<< len, ++i, key[i], hash+key[i], and hash=hash+key[i]. We therefore have 5 instructions being executed once for each of the len (n) iterations of the loop.

Adding up, we get about 2 + (1 or 2) + (4 or 5)n, so that 3 + 4n <= T(n) <= 4 + 5n. 3 + 5n is reasonable; the exact answer depends on how you are counting individual instructions. A more detailed model might count simple assignments as requiring less time than e.g. the modulo operation...