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

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