CODEWITHSUNDEEP
pythonbig-o
xuxu
xuxu

Reputation: 823

Determining the big-O runtime of the loop?

Q. What is the worst-case big-oh runtime of the following, in terms of N? Assume x is a positive integer where N = math.log(x, 2).

def bigOh(x):
    c = 1
    while (x > 0) :
        (x, c) = (x // 42, c + 1)
    x = 1
    while (x ** 2 < c) :
        x += 1
    return x

I'm having trouble computing the number of steps involved the second while loop. The first one should execute a log x / log 42 number of times i.e. in O(N).

For the second loop, the check (x + n) ** 2 < c is made each time, where n is the nth iteration, but I'm pretty much stuck after this.

Can anyone please help?

Edit: The first loop runs in O(N) instead of O(log N) as pointed out in the comments.

Upvotes: 0

Views: 372

Answers (1)

extratype
extratype

Reputation: 92

The first loop executes log x / log 42 times. In terms of N = log x / log 2, that's just O(N) time.

After the first loop, c ~ O(log x). The second loop terminates when x ~ sqrt(c). Thus it should loop around sqrt(c) times, which is O(sqrt(log x)) = O(sqrt(N)). Therefore the total running time of bigOh is O(N + sqrt(N)) = O(N).

Upvotes: 2

Related Questions