worst case/best case confirmation

I would like to confirm my ideas are correct for worst case/best case scenarios of the following code:

def function2(L, x):
ans = 0
index = len(L)
while (index > 0):
    i = 0
    while i < 1000000:
        i = i + 1
    ans = ans + L[index - 1]
    index = index // 2

if (x == L[-1]):
    return ans
else:
    for i in range(len(L)):
        ans = ans + 1
return ans

I would think that best case would be O(sqrt(n)) because index // 2 is the factor at which it would best. I think worst case would be o(n+sqrt(n) because the else statement is adding constant runtime. Would this be correct?

---

I would think that best case would be O(sqrt(n)) because index // 2 is the factor at which it would best.

Not quite sure what you mean by "index // 2 is the factor at which it would best". No matter what input you have, index // 2 is going to be the "factor" for best/worst/average case.

index is going to be cut in half with each iteration, so your loop's complexity is not sqrt(n) but log(n) . (Look here for a more detailed explanation of why.)

I think worst case would be o(n+sqrt(n) because the else statement is adding constant runtime.

Be extremely careful with your usage of "O" vs "o". Little-o is a completely different notation altogether and you don't want to get them confused. (Also adding an n to your complexity is not a adding a constant runtime, n is a variable not a constant)

Big-O is an inclusive upper bound so for the :

Best case , when x == L[-1] , the code runs in O(logn) time.

Worst case , when x != L[-1] , the first loop runs in O(logn) time and the second loop runs in O(n) time. Since Big-O is looking for the upper bound since we know O(n) takes more time than O(logn) our complexity is simply O(n)

链接地址: http://www.djcxy.com/p/39902.html

上一篇: 什么时候一个人通常喜欢那么一点

下一篇: 最坏情况/最佳情况确认