1

I know that big O notation is a measure of how efficint a function is but I don\t really get how to get calculate it.

def method(n)
   sum = 0
   for i in range(85)
       sum += i * n
   return sum

Would the answer be O(f(85)) ?

1
  • The runtime here appears to be constant (i.e. invariant of n)... Dec 11, 2013 at 20:12

4 Answers 4

4

The complexity of this function is O(1)

in the RAM model basic mathematical functions occur in constant time. The dominate term in this function is

for i in range(85):

since 85 is a constant the complexity is represented by O(1)

1
  • 1
    Can you explain why ?
    – kiasy
    Dec 11, 2013 at 20:16
3

you have function with 4 "actions", to calculate its big O we need to calculate big O for each action and select max:

  1. sum = 0 - constant time, measured O(1)
  2. for i in range(85) - constant time, 85 iterations, O(1 * complexity of #3)
  3. sum += i*n - we can say constant time, but multiplication is actually depends on bit length of i and n, so we can either say O(1), or O(max(lenI, lenN))
  4. return sum - constant time, measured O(1)

so, the possible max big O is #2, which is the 1 * O(#3), as soon as lenI and lenN are constant (32 or 64 bits usually), max(lenI, lenN) -> 32/64, so total complexity of your function is O(1 * 1) = O(1)

if we have big math, ie bit length of N can be very very long, then we can say O(bit length N)

NOTE: bit length N is actually log2(N)

3
  • ... and the O(log2 n) is equal to O(log n).
    – pepr
    Dec 11, 2013 at 21:01
  • 1
    @pepr in math world it is better to mention log base, because just log usually mean log10, but in computer science world log usually means log2. so I prefer to indicate base here (of course you can convert from log2 to log10 via const, and then just write log without base) Dec 11, 2013 at 21:21
  • I know you know. :) And any constant does not change the O().
    – pepr
    Dec 11, 2013 at 21:29
1

In theory, the complexity is O(log n). As n grows, reading the number and performing the multiplication takes longer.

However, in practice, the value of n is constrained (there's a maximum value) and thus it can be read and operations can be performed on it in O(1) time. Since we repeat an O(1) operation a fixed amount of times, the complexity is still O(1).

Note that O(1) means constant time - O(85) doesn't really mean anything different. If you perform multiple constant time operations in a sequence, the result is still O(1) unless the length of the sequence depends on the size of the input. Doing a O(1) operation 1000 times is still O(1), but doing it n times is O(n).

If you want to really play it safe, just say O(∞), that's definitely a correct answer. CS teachers tend to not really appreciate it in practice though.

0

When talking about complexity, there always should be said what operations should be considered as constant time ones (the initial agreement). Here the integer multiplication can be considered or constant or not. Anyway, the time complexity of the example is better than O(n). But it is the teacher's trick against the students -- kind of. :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.