Question

Please can someone tell me whats the Big O notation of and why:

def h(x):
assert type(x) == int and x >= 0
answer = 0
s = str(x)
for c in s:
answer += int(c)
return answer

Answer 1

I'd rate it On. The loop iterates len( x ) times ( n ).

Answer 2

Thank you very much, I read it somewhere (sorry I don't remember where, I was rereading my notes to restart seeing the lectures of 6.00) that said it whas O(log2n) then I became confused. By the way log2n means that it is log base 10 of 2n or that its is log base 2 of n?

Answer 3

I am also trying to understand Big O notation. My take on it is that every step in the function except the for loop is executed once and constant time. The for loop has to travel down the whole length of the string so the number of steps is the length of the string. So, I would say it's O(len(s)). I think O(n) is the general way to state this as long as it's understood that n is the length of s.

As for the O(log2n), I don't think there is enough information to tell for certain. I'm not sure how I would guess the answer. Usually, they just talk about log in general without even mentioning the base but they also don't bother to distinguish between n and 2 * n.

I'm still pretty new and make a lot of mistakes so this is just my two cents worth. Please feel free to correct me.

Answer 4

Big O notation can be a real joy. On is a constant amount of work and the length of work is dependent upon what's given to it.

O(log2n) is for things like a binary search where you'll have a maximum of log2n tries to finish. For instance, if you were searching an ordered list of elements, using a binary search you would find an element in <=8 tries.

On2 is the one to watch out for. Nested loops, say 10 and 10 would take 100 to finish. On larger datasets, say a million, these differences DO add up.