-3

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?

Robert Harvey
  • 198,589
  • 55
  • 464
  • 673
Maverick Meerkat
  • 95
  • 3
  • 2
    Possible duplicate of [What is O(...) and how do I calculate it?](https://softwareengineering.stackexchange.com/questions/132331/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 [softwareengineering.se], 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. – Maverick Meerkat 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 01 '19 at 04:04
  • @RobertHarvey: If that is indeed what the OP is asking, then it is important for the OP to clarify, since we *typically* use Big Oh notation for describing the growth rate of the computational complexity of an algorithm, not for the growth rate of the function that is computed by the algorithm. – Jörg W Mittag Jul 01 '19 at 06:17

1 Answers1

3

  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)).

Deduplicator
  • 8,591
  • 5
  • 31
  • 50