Python Complexity (Runtime)

Question

def f2(L):
    sum = 0
    i = 1
    while i < len(L):
        sum = sum + L[i]
        i = i * 2
    return sum

Let n be the size of the list L passed to this function. Which of the following most accurately describes how the execution time of this function grows with increasing n?

(a) It grows linearly, like n. (b) It grows quadratically, like n ^ 2.

(c) It grows less than linearly. (d) It grows more than quadratically.

I do not understand how you determine the relationship between the execution time of a function and the growth of n. Can someone please explain this to me?

Answer 1

ok, since this is homework:

this is the code:

def f2(L):
    sum = 0
    i = 1
    while i < len(L):
        sum = sum + L[i]
        i = i * 2
    return sum

obviously depends on len (L).

So, let's look at each line what it costs:

sum = 0
i = 1
# [...]
return sum

this is obviously a constant time independent of L. In the cycle we have:

    sum = sum + L[i] # time to lookup L[i] (`timelookup(L)`) plus time to add to the sum (obviously constant time)
    i = i * 2 # obviously constant time

? L. loops(L)

loops(L) * (timelookup(L) + const)

, , python,

O(loops(L)) ( , O)

, len() L?

(a) , (b) , ?

(c) , (d) , (b)?

Answer 2

, , , , - .

, , , , .

, 1 . 1. , , - , .

Big O: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

O (1) ( AD), , L. , while i L. , i , , , , L. , , while len (L), . 1 1 while.

, - , .

, ch3ka, , , with, . list L[i] , , .

Answer 3

:

import matplotlib.pyplot as plt

def f2(L):
    sum = 0
    i = 1
    times = 0
    while i < len(L):
        sum = sum + L[i]
        i = i * 2
        times += 1    # track how many times the loop gets called
    return times

def main():
    i = range(1200)
    f_i = [f2([1]*n) for n in i]
    plt.plot(i, f_i)

if __name__=="__main__":
    main()

...,

- L, - ; big-O .

Answer 4

, n = 10. , , 20. ? . 4 , . Etc.

Answer 5

When you look at a function, you must determine how the size of the list will affect the number of loops that will occur.

In your specific situation, let's increase n and see how many times the while loop will work.

n = 0, loop = 0 times
n = 1, loop = 1 time
n = 2, loop = 1 time
n = 3, loop = 2 times
n = 4, loop = 2 times

See the template? Now answer your question:

(a) It grows linearly, like n does. (b) It grows quadratically, like n^2 does.

(c) It grows less than linearly. (d) It grows more than quadratically.

Checkout Hugh for an empirical result :)

Answer 6

it O(log(len(L))), since list browsing is a constant-time operation, independent of the size of the list.