# What is the O of this operation?

Say for a given positive integer number `n`, you have to find a level `k` so that

`1 + 2 + 3 + ... + k = S` is below or equals `n`

but `S + k + 1` is above `n`.

For example in python:

``````def find_level(n):
level = 1
while n > 0:
n -= level
level += 1
return level - 1
``````

What is the O magnitude of this function?

• Possible duplicate of What is O(...) and how do I calculate it? – gnat Jun 30 '19 at 13:26
• Big Oh notation is simply a notation to concisely express the growth rate of a function. You are asking about the Big Oh notation, i.e. the growth rate of some function, but you are not actually telling us what function you want to know the growth rate of. Also, Big Oh notation has nothing to do with Software Engineering, it is simple mathematics. – Jörg W Mittag Jun 30 '19 at 13:26
• @JörgWMittag I just showed you the function (find level). Big-O is a software engineer related term. FYI - arrogance is not very helpful. – David Refaeli Jun 30 '19 at 13:41
• `find_level` is not a function in the mathematical sense. It is an algorithm. Big Oh only works to describe the growth rate of mathematical functions. So, do you want to describe the growth rate of the function that is computed by the `find_level` algorithm? – Jörg W Mittag Jun 30 '19 at 15:13
• @JörgWMittag: That seems like a distinction without a difference. If what you consider the correct wording is "the growth rate of the function that is computed by the `find-level` algorithm," then yeah, that's what he wants. I'm not a mathematician; I would call it "the Big O of the function," and would feel just fine doing so. – Robert Harvey Jul 1 '19 at 4:04

1. Simplify:

``````def find_level(n):
level = 0
while n > 0:
level += 1
n -= level
return level
``````
2. Get the closed form for the highest `n` per `level`:

n = sum(x = 0 to level, x) = level * (level + 1) / 2

3. Solve that for `level` using the quadratic formula or some other method:

0.5 * level2 + 0.5 * level - n = 0

level = -.5 + sqrt(.25 + 2 * n)

• If you're going to do that analysis though, why not just return the closed form for `level` and make the algorithm `O(c)`? – Philip Kendall Jun 30 '19 at 15:17
• Well, I derived the closed form for `level` to determine the order of the given algorithm. The trivial step of actually using it directly, I leave to the observant reader. One just has to beware of the implementations limitations, regarding square-root and general floating-point. – Deduplicator Jun 30 '19 at 16:00