0

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

  • Sorry, I meant "constant", meaning they are not being multiplied or exponentially increased by another value. –  Feb 24 '18 at 15:50
  • 1
    Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Bernhard Barker Feb 24 '18 at 15:50
  • So you got `O(3n + 2)` there. Now you ignore the constants and you're left with `O(n)`. – Sergio Tulentsev Feb 24 '18 at 15:51

1 Answers1

2

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.

Olivier Melançon
  • 21,584
  • 4
  • 41
  • 73