CODEWITHSUNDEEP
python-3.xbig-operformance
kiasy
kiasy

Reputation: 304

What would be the big O notation for the function?

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)) ?

Upvotes: 1

Views: 901

Answers (4)

pepr
pepr

Reputation: 20762

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. :)

Upvotes: 0

kviiri
kviiri

Reputation: 3302

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.

Upvotes: 1

robbmj
robbmj

Reputation: 16506

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)

Upvotes: 4

Iłya Bursov
Iłya Bursov

Reputation: 24146

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)

Upvotes: 3

Related Questions