(Almost) Daily Algorithm Practice: Big O and square roots

Here is today's problem. I was definitely off-base on my first attempt at analyzing the runtime! 



But when you realize what this is doing, it's not too bad. While of course in a real programming scenario we'd just use one of the built-in square root functions, well...Someone has to code those to work in the first place! And this is a possible implementation of one. 

If you notice, the algorithm is essentially dividing the problem space into two pieces and analyzing them, effectively running a binary search. This was my initial mistake. I stepped through the problem, was doing all this division crap, forgetting that it's not about the operations that the algorithm itself is running, but rather the approximate number of times it is running said operations. 

So, it's a binary search, basically to the T. There is nothing special here. Consequently, we can conclude that the runtime is O(log n). 

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