5 
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 runtime of this function grow as n grows?

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

I don't understand how you figure out the relationship between the runtime of the function and the growth of n. Can someone please explain this to me?

Improve this question
2

6 Answers 6

Reset to default
12

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

it is obviously dependant on len(L).

So lets see for each line, what it costs:

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

those are obviously constant time, independant of L. In the loop 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

and how many times is the loop executed? it's obvously dependant on the size of L. Lets call that loops(L)

so we got an overall complexity of

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

Being the nice guy I am, I'll tell you that list lookup is constant in python, so it boils down to

O(loops(L)) (constant factors ignored, as big-O convention implies)

And how often do you loop, based on the len() of L?

(a) as often as there are items in the list (b) quadratically as often as there are items in the list?

(c) less often as there are items in the list (d) more often than (b) ?

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

10

I am not a computer science major and I don't claim to have a strong grasp of this kind of theory, but I thought it might be relevant for someone from my perspective to try and contribute an answer.

Your function will always take time to execute, and if it is operating on a list argument of varying length, then the time it takes to run that function will be relative to how many elements are in that list.

Lets assume it takes 1 unit of time to process a list of length == 1. What the question is asking, is the relationship between the size of the list getting bigger vs the increase in time for this function to execute.

This link breaks down some basics of Big O notation: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

If it were O(1) complexity (which is not actually one of your A-D options) then it would mean the complexity never grows regardless of the size of L. Obviously in your example it is doing a while loop dependent on growing a counter i in relation to the length of L. I would focus on the fact that i is being multiplied, to indicate the relationship between how long it will take to get through that while loop vs the length of L. Basically, try to compare how many loops the while loop will need to perform at various values of len(L), and then that will determine your complexity. 1 unit of time can be 1 iteration through the while loop.

Hopefully I have made some form of contribution here, with my own lack of expertise on the subject.

Update
To clarify based on the comment from ch3ka, if you were doing more than what you currently have inside your with loop, then you would also have to consider the added complexity for each loop. But because your list lookup L[i] is constant complexity, as is the math that follows it, we can ignore those in terms of the complexity.

Improve this answer

Comments

4

Here's a quick-and-dirty way to find out:

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

... which results in

plot of function loops vs parameter size

Horizontal axis is size of L, vertical axis is how many times the function loops; big-O should be pretty obvious from this.

Improve this answer

4 Comments

This seems to be correct only because list lookup is O(1), as ch3ka points out. More generally, it's not the number of iterations that we need to measure, but time. It could be measured directly and plotted with matplotlib as well, though.
Because list lookup is O(1), we're able to assume that the number of iterations will be ~= to the time taken. The question was specifically about lists as well.
@g19fanatic That's right, but the OP could be unaware of that fact, so I thought it was worth to point out that subtle difference. It's an implied step in the logic that I wanted to become more explicit, that's all.
you should really point out that this only works because L[i] is O(1)
3

Consider what happens with an input of length n=10. Now consider what happens if the input size is doubled to 20. Will the runtime double as well? Then it's linear. If the runtime grows by factor 4, then it's quadratic. Etc.

Improve this answer

Comments

2

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

In your specific situation, lets increment n and see how many times the while loop will run.

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 pattern? Now answer your question, does it:

(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's answer for an empirical result :)

Improve this answer

Comments

0

it's O(log(len(L))), as list lookup is a constant time operation, independant of the size of the list.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.