CODEWITHSUNDEEP
python-3.xbig-o
user6217340
user6217340

Reputation:

Big O Complexity

I'm trying to understand Big O and thought stepping through a simple program might help.

def sum(n):
    k = 0
    j = 0
    while k < n:
        k = k + 1
    while j < n:
        j = j + 1
        k = k + j
    return k

k and j are initially assigned the value 0, which counts for 2 assingments, the first while loop performs 1 assignment n times and second while performs 2 assignments n times. So the expression would be 2 + n + 2n.

Because the first two terms in the above expression (2 and n) are constant, they will become insignificant compared to the third term, which multiples n by 2 as n grows. So the Big O for the code would be O(2n).

Is my logic and answer correct? Thanks in advance

Upvotes: 0

Views: 157

Answers (1)

Olivier Melan&#231;on
Olivier Melan&#231;on

Reputation: 22294

Your answer is correct, although we do not say O(2n), but O(n) instead.

What O(n) means is that the worst case time complexity of your algorithm increases at most linearly, that is it is eventually bound by some function of the form a * n where a is some constant. The actual constant is not relevant for the big-O notation.

To be more technical, I say eventually because we are talking about what we call the limiting behaviour of your algorithm, you can think of it as describing the behaviour only for very big inputs.

By example in you algorithm, as n grows, we care less and less about the assignations k = 0 and j = 0, they become negligible.

In conclusion, the big-O notation aims to describe the speed at which the running time grows, not to describe precisely the what the run time is.

Upvotes: 2

Related Questions