Big O and the Powerball
A few months ago I tasked myself with making a program that produced all of the possible Powerball outcomes. What purpose does this serve? Well it’s just the first step of a bigger idea: calculating the total winnings of a person who bought every possible ticket. Is it possible for someone to buy every single ticket? Sure, with enough money, of course. But how much would it cost? Well, given that winning the Powerball is a 1 in 292,201,338 chance that’s 292,201,338 tickets at a price of $2 a piece, you would need $584,402,676. So, sure, it’s possible but not likely. But let’s get back to the point, time to produce every outcome in Javascript.
Prior to my enrollment in General Assembly I had been experimenting with programming in general and decided to build this program in Javascript. So I took what little I knew and pulled up an IDE for phones called Dcoder and plugged away. My first thought was to make an empty array, randomly generate 5 numbers, none repeating, using .push to put them into the empty array, sort that array low to high, then push that array into a bigger array to continue making arrays(tickets). I didn’t forget the Powerball number I just chose to omit it for the time being, so bear with me. Alright so let’s take a look at what that looks like.
This is hard to read, let me fix that then I can run you through my thought process.
Ok, that’s at least more readable. So what’s happening here?
line 2: I’m declaring a new set using the Javascript global object Set to store all the tickets that get generated, which would ensure that I don’t get any duplicate tickets.
Line 3: I initialize the main function.
Line 4: I declare an empty array to start things off.
Line 5: we start a while loop to fill the array with random numbers from a the range of 1 to 69.
Line 10: I sort the array to be in ascending order.
Line 13: doesn’t do anything…I don’t know what I was doing there. Ignore that.
line 14: We add the array to the set.
Line 16: We initiate a conditional statement for writing all of the items in set to the console.
That seems to make sense, or at least it did when I made it. Let’s give it a go.
Well that’s no good. So what’s wrong with our code? It’s not an infinite loop, we have an exit if scenario that happens when the set is equal to the max number of possible tickets 292,201,338. Based on Big O notation this function has linear complexity or O(n).
So according to the chart above linear complexity should be good right? If that were the only factor sure, but alas that is not the case. In this scenario we ran into the max call stack size which varies based on browser, but normally lands somewhere in the thousands, not the millions. Clearly I needed to refactor, break up the problem. Did I? Nope. I learned Javascript, not algorithms or Big O so at the time I didn’t know what to do, so I set it down to come back to later.
…much later.
Several months pass, I start my coding bootcamp and we begin to learn some more about Javascript. I catch on real quick because I’ve been here before and my classmates keep asking what my background is and why I get everything so easy. I tell them about my attempts at using Javascript and the Powerball, and it sparks my interest to revisit it. I remember that my code was randomly creating numbers and that it was inefficient at creating the arrays, so I puzzle over the idea of iterating the results instead. I test out a simple while loop to figure out how to iterate through all of the numbers, this time including the Powerball.
Line 7: Define an empty array to store all the tickets we produce.
Line 8: Define a baseline ticket, no ticket can be lower than this.
Line 10: simple function to set the Powerball to the lowest number it can be, push the array, then loop, increasing the Powerball then pushing it.
Sounds good, run it.
It works! Next step iterate on the numbers before that at the same time. Easy.
This one is a little harder to follow, but increaseTix4 iterates through the ticket number at position 4 on the array, iterating through the Powerball each time ticket[4] is increased. increaseTix3 iterates through the third item, each time iterating through ticket[4] which iterates through Powerball, which pushes the array to allOutcomes. Wait, what? I know I know, Just watch.
It works! At 1689 and 1690 you can see that ticket[3] is increased to 5 and ticket[4] is reset to 6 now iterating through those possibilities. Good, great, grand! It works, scale it up, it’s time to do all of the numbers.
and the finishing touch, in order to get these to all generate the tickets in order we have to call them in order.
Great! Let’s fire off that function and see what happens. As long as the computer has enough power it should work right? What could go wrong?
I fire it off and I see nothing, no output. I wait a minute, still no output but my laptop fan just kicked into overdrive(see image). I wait another minute, still nothing. My client has frozen, I have to close the window. So what happened? Having not learned about Big O yet I just figure I need to break it into pieces. I try that and go down the line, but regardless I still get to a point where it freezes. I figure I’d call it a night and try it again the next day. The next day comes and I figure I should do my assigned homework, “Algorithms and Big O notation.” I read through it when I get to a part that gives examples of Big O complexity, when I realize the program I made just the day before was factorial. And then the homework smacks me in the face with the cold hard truth.
…oh, uhhhhh oops.
So what did I learn from this? Well for one we’re not at the point where computers have unlimited resources to process programs. In addition to the importance of breaking the workload down so that my simple computer can handle my request. Let’s take a look at that chart again.
As you can see my factorial function(represented by O(n!)) is the worst as it skyrockets into the space.
But Zach, it worked the first few times! Why not this time?
Ok, so here’s whats happening. First we ask the program to run powerball(), producing 26 array items. Then the increaseTix4(), producing 1,663 array items. Then increaseTix3(), producing 54,106 array items. Then the next one, and the next one all the way until we get to our grand total request of 292,201,338 items. Sure the computer could handle a few thousand requests at first but it can’t handle hundreds of millions(yet). So we have to chop our function up into tiny pieces so it can handle them one at a time. Could you imagine the stress of having to write out over 200 million sets of numbers over the course of a few minutes? You couldn’t. And neither can a computer, at least not like that. So what’s the next step? I don’t know yet. Clearly something has to change but I haven’t learned exactly how best to improve it to get the result I want. So for now we’ll just say.
