CODEWITHSUNDEEP
pythonbig-o
Bitharp
Bitharp

Reputation: 31

What is the big O of this function?

def fd(n):
    x,y,count1,count2 = n,1,0,0
    while (x > 1): (x,count1) = (x/5,1+count1)
    while (y < n): (y,count2) = (count1+y,1+count2)
    return count2

Upvotes: 1

Views: 823

Answers (2)

jimifiki
jimifiki

Reputation: 5534

I want to point out that the answer to this question depends on an agreement about what we are talking about (is important the fact that double numbers are going to be manipulated? do you want a theoretical answer that could sound unsatisfactory or a practical answer?)

Please, let me rephrase this answer: https://stackoverflow.com/a/2027842/512225 :

People play a bit fast and loose with big-O notation.

Algorithmic complexity, and hence big-O notation, should be stated in terms of the size in bits of the input, not in terms of the values of the input. Assuming binary input and arbitrarily-large numbers, and N the number of bits of input, N = log(n). The complexity is O(exp(N)/N) = O(exp(N)/N) since the second loop requires n/log(n) steps = exp(N)/N steps.

In practice it makes sense to talk about complexity as though N were the input itself, not the size of the input. In that case the complexity of your function is n/log(n).

Anyway we are disregarding the issues given by the fact that n is limited by the definition of double, so that strictly speaking it does not make sense to talk about the asymptotic behavior (with n -> infinity). And we disregard also the fact that if your input is a double them its size is constant and so the complexity of your algorithm is (strictly speaking) O(1) (huge_constant times 1) with huge_constant equal to worst case time (that constant probably depends on the largest number you can express with Python's doubles).

Summarizing:

the formal answer is O(1) but O(exp(N)) is not that bad as answer, O(n/log(n)) is a good answer too (and probably what you really need).

Upvotes: 0

Ted Hopp
Ted Hopp

Reputation: 234795

Let's see. The first loop counts how many times n can be divided by 5, so count1 is log(n) (constants don't count for O() calculations). Then the second loop counts how many times count1 (= log(n)) can be added to 1 to get to n, so it basically loops for n / log(n) times.

It looks to me like this is O(log(n) + (n/log(n))).

As J.F. Sebastian points out, n/log(n) dominates log(n), so the final answer should be O(n/log(n)).

Upvotes: 10

Related Questions