Daily Algorithm Practice: Cracking the Coding Interview, VI.12

 


Merge sort by itself is O(n log n) so O(b log b) in this case. How do I know? I looked it up. :P Specifically, there are log n levels of the tree, and for each level, the tree performs an O(n) operation. more info

That for loop is O(a * log(b)). Because it does the O(log(b)) binary search for every iteration, and it iterates O(a) times. 

So O(b log b) + O(a log b). Neither of these terms can be dropped. Combined, we have O(b log b + a log b). 

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