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?

  • 2
    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
  • 3
    @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)

Your algorithm is obviously O(sqrt(n)).

| improve this answer | |
  • 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
  • 1
    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
  • @Deduplicator so your closed form is also O(sqrt(n))? – David Refaeli Jun 30 '19 at 16:29
  • @DavidRefaeli No, Philip got it right. – Deduplicator Jun 30 '19 at 16:45
  • @Deduplicator ok, cool. So I assume that finding sqrt of a number is an operation in constant time? – David Refaeli Jul 3 '19 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.