## Big O (for all problems)

For questions about problems on the Project Euler web site. No spoilers. Please include the question number in the subject line of your post.

### Big O (for all problems)

Hi again,

We have talked several times about Big O, but it stills difficult sometimes to find a suitable function for what we are looking for. I thought about using this post for puting the codes we need to improve with a Big O, and the other users can help us to make them better. Looking at our and the rest of users' problems we can really improve our skills at using Big O.

I will start puting the code I am working at now (Problem 12). Notice that you should not continue reading if you have not completed this problem (in order to avoid code-spoilers):

Code: Select all
`triangulos = []for x in xrange(1,9999):   y = sum(i for i in xrange(1,x+1))   triangulos.append(y)lista = []factores = []for x in triangulos:   for i in xrange(1,x+1):      if x%i == 0:         factores.append(i)   if len(factores) >= 500:      result = x,factores      del(factores)      factores = []      lista.append(result)      del(result)      break   elif len(factores) < 500:      del(factores)      factores = []`

I put the whole code because as a beginner I am at Big O, I do not really know where should I improve it.

According to other posts, I tried something like using sqrt(), and although it run really fast, it did not give me a suitable result. So I would be pleased if you can help me to "open my mind" to new ways of using Big O.

Thank you very much.

Posts: 14
Joined: Mon Aug 25, 2014 9:32 am
Location: Spain

### Re: Big O (for all problems)

I think it would be best if you refactored your code to use functions, and then put doc strings on those functions indicating their Big O and then we give you feedback from there. How does that sound?
Due to the reasons discussed here we will be moving to python-forum.io on October 1, 2016.

This forum will be locked down and no one will be able to post/edit/create threads, etc. here from thereafter. Please create an account at the new site to continue discussion.

micseydel

Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

### Re: Big O (for all problems)

Alright.

Code: Select all
`triangulos = []def triangulos(z):   for x in xrange(1,z): """O(x)"""      y = sum(i for i in xrange(1,x+1)) """O(sum(1 until x)) < O(x**2)"""      triangulos.append(y)lista = []factores = []`

And now I have a problem, because if I put this:

Code: Select all
`def getfactors(x):   for i in xrange(1,x+1): """O(x)"""      if x%i == 0:         factores.append(i)`

inside here:

Code: Select all
`for x in triangulos:   getfactors(x)   if len(factores) >= 500:      result = x,factores      del(factores)      factores = []      lista.append(result)      del(result)      break   elif len(factores) < 500:      del(factores)      factores = []`

it gives me this error:

Traceback (most recent call last):
File "<pyshell#26>", line 1, in <module>
for x in triangulos:
TypeError: 'function' object is not iterable

But I also can't put it out of there. Otherwise, if I loop without adding-checking-deleting, the factores list would grow and grow.

So I see my first problem would be to make the suitable definitions, but also how to improve these Big O.

Posts: 14
Joined: Mon Aug 25, 2014 9:32 am
Location: Spain

### Re: Big O (for all problems)

Code: Select all
`triangulos = []def triangulos(z):`

See how triangulos is first just an empty list, but then a function is defined with the same name? This error has nothing to do with big O. Give them a different name.
Due to the reasons discussed here we are moving to python-forum.net on October 1, 2016.

This forum will be closed. Please create an account at the new site to continue discussion.

IRC://irc.freenode.net/python-forum
Kebap

Posts: 689
Joined: Thu Apr 04, 2013 1:17 pm
Location: Germany, Europe

### Re: Big O (for all problems)

Well, it is true, sorry. But I did it just because micseydel ask me to def them. But you can check at my first post that my problem is with Big O I think we can assume that def is a minor problem.

So I would really thank you if you can help improving the Big O(s) of the first code I posted

Edit: The first code I copied works 100% perfect for smaller numbers (as 100 instead of 500). So according to what I learnt until now, what we should do is to improve the Big O in order to make it faster.

Posts: 14
Joined: Mon Aug 25, 2014 9:32 am
Location: Spain

### Re: Big O (for all problems)

I think it'd be easier for you to understand Big O if you're able to analyze your own code, which will be easier if you can make your code more readable, namely with functions. But you don't want to use global variables, which defeats the purpose of trying to clean up code. If you're not familiar with functions, you should probably try a tutorial since you'll find the effort will pay off quickly and help a great deal in the future.
Due to the reasons discussed here we will be moving to python-forum.io on October 1, 2016.

This forum will be locked down and no one will be able to post/edit/create threads, etc. here from thereafter. Please create an account at the new site to continue discussion.

micseydel

Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA