Daily algorithm practice: Runtime analysis

From Cracking the Coding Interview: 

I had to peek at the solution for this one, but it makes sense now. This may not be the best explanation but I'm sure I'll get better as I go along. Also, when I get to the true exercises (instead of just the examples) I will probably put them on my GitHub as well. But not for the examples. 

In this algorithm, we will be repeatedly dividing by 2. We will keep recursing until we can't divide by 2 anymore. And when we have an algorithm in which we keep diving by 2, this is a pretty clear indicator of O(log n) runtime. Why? Because if we kept multiplying by 2 repeatedly, that would be an exponential runtime. Logarithms are the opposite of powers, we are diving here, and multiplication is the opposite of division. Ergo, logarithmic runtime. 

Comments

Post a Comment

Popular posts from this blog

6 hours and only 6 Lagoon rides?

Just saw this in a FB comment. That's really unfortunate for the family who experienced this. I usually go to Lagoon on the most crowded day of the week, Saturday, and I'm almost certain that I could beat that even in the middle of July (but maybe not October. People LOVE the Halloween/Frightmares post season) Like the general principles are pretty easy. GRANTED I usually do Lagoon solo and these strategies are going to be harder to execute with a group that consists of anyone other  than extremely energetic teens and adults.  Rope drop and speed-walk and you can have all the coasters plus Samurai and both sides of Rocket done by 1-2 pm.  In order to rope drop, you will need to get there no later than 9:45 AM and the closer you cut it, the faster you are going to have to walk.  Potential order: Primordial (skip if there's even a single breakdown or if you don't get there at literal rope drop , like you actually see the rope fall  and almost get trampled by a bun...
Read more

Reflecting on major life goals yet again

And what I need to do daily to achieve them.  I feel like I write these a lot. I probably just need to find something that works and stick to it. Therein lies the rub, though. I have been steadily improving, but I still am not moving at what I would consider to be a "going to make it in a reasonable amount of time" cadence.  So, here we go again. I will keep iterating until I get something that sticks. Since I'm working tonight but not actively doing anything just yet while the code is deployed. And since I'm caffeinated on a Sunday, which is rare (and may take tomorrow off to reset the adenosine receptors).  Sundays are always a weak day for me. That's fine -- day of rest and all -- but I would like to start making at least some form of forward momentum.  Goal #1:   Published novelist, artist, and game dev.  It's always been my goal to be a writer, ever since the second grade. Art and game dev came later, in late high school / early college. The goal is t...
Read more

Hobble Creek Half: The slow passage of time marches us towards our inevitable death

Image
or, how I almost died alone in a Honey Bucket porta potty (to be fair, if you are not alone in there that is kind of weird) and lost 3/4 of a summer Saturday and 1/4 of Sunday to dying in various toilets but at least got my Elite 100 medal hell yeah See, I couldn't PR because I had to finish in 6:21 pace. For the memes! * So, in June I ran the Timp Half. No issues. 1:23:55. Course PR. I slowed down after the initial smooth downhill out of the canyon, as designed. I felt a calf cramp coming on, so I slowed down just a tad, was fine, and didn't have to plod my way to the finish line. Runtastic Events always does a great job.  Then on Saturday I ran the Hobble Creek Half in 1:23:09 (so 7 seconds off my PR) and almost died. In fact, I am currently still dealing with the after effects of whatever just happened to my body.  Let us see exactly how the wheels came off:  It was BREAKFAST. Yeah, I screwed that up.  What I had: * 180 mg Crystal Light Energy * 1/4 Bucked Up...
Read more