(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

Unleashing my inner Disney Princess ✩₊˚.⋆☾⋆⁺₊✧ at the 2024 Disney Princesses Half Marathon

Image
TL;DR it was amazing and perfect  and we are going to make this an annual tradition. I may edit this with photos later, but I'm probably going to forget.  Recently, I spent 5 wonderful days donating my dollarbucks and soul to the evil mouse in Orlando. I did it for the Disney Princess Half Marathon.  Just look at that happy little alligator musician. He's so CHONKY. It's adorable. I love him. How could you NOT run a half marathon for him when he's cheering you on?  (My dad says it's weird to say the word "adorable" as a man, which makes zero logical sense and obviously means I need to use that word as often as possible. I will also continue to wear my rings and maybe I'll start flashing my pink protein shaker. Just to cause a little discomfort, because it's funny.)  I haven't seen the movie yet actually so idk if the gator is a major character or not. But JUST LOOK AT HIM.  My cousin and I had been planning a Disney trip, specifically centered
Read more

The 20-something types of Computer Science majors

Image
I've been way too distracted with this blog lately, and I need to hurry up and start getting crap done. But...I've been dying to write this lol.  The advanced neckbeard A rare variety. When a neckbeard is forced out of his mom's basement and into college, he becomes an Advanced Neckbeard. You can always tell when he's coming, because you can smell him from half a mile away. He is very overweight, and wears shirts that are either plain or adorned with anime/gaming graphics. These shirts are either stained with sweat, Hot Cheetos, or something a little bit more, ah, suspicious . He is so socially unskilled that he makes everyone else in the major look normal. Age 30+, GPA at a 2.0 or just barely above it. Will never drop the major despite his lack of effort, because he simply doesn't care if he gets bad grades. In fact, he is probably highly intelligent, but his grades will never reflect that. Nevertheless, he will get a much higher paying job than a regular neckbeard
Read more

The Evenstar

I've never liked this world much.  Ever since I was a little kid, I always dreamed of going somewhere else. I created this alternate version of Earth that had everything and everyone that I loved, but with all these improvements to it. Magic was real. So were dragons. Dinosaurs hadn't gone extinct. Technology allowed people to fly. A network of glass corridors provided transport between this world and mine, snaking through streams of stars, galaxies, and lightyears of blackness.  And more than anything, I wasn't alone. I don't remember why I spent so much time alone as a kid. I really wish I did. All I know is that when I was in my  world, I always had someone by my side.  The feeling of being out of place here was overwhelming. It still is. That sense of not belonging, of longing for somewhere else, it has never gone away.  When I was in middle school, being bullied daily, I escaped to that world. The boys who tripped me and spit on me disappeared, replaced by tropical
Read more