Asymptotics Practice
Last updated
Was this helpful?
Last updated
Was this helpful?
Make sure to review before proceeding with these problems.
Asymptotics is a very intuition-based concept that often doesn't have a set algorithm for computing. The best way to get good at analyzing programs is to practice!
With that said, here are some problems of increasing difficulty for you to enjoy 😊
What runtime does this function have?
What runtime does this function have?
I've tweaked the previous problem a little 😁 Try to spot the difference and see if it changes the runtime at all!
TREEEEEEEEE recursion 🌳🌲🌴
Let's replace the 4 in the previous problem with n and see what insanity ensues.
Here's a case where the best case and worst case runtimes are different. Can you figure out what they are? (Let n = items.length
).
Here's a mutual recursion problem! What are the best and worst cases for explodeTNT(n)
? What are their runtimes?
These problems are quite difficult. Don't be concerned if you don't feel confident in solving them (I certainly don't).
A huge disaster :ooo
Congrats for making it this far! By now you should be an expert in asymptotic analysis :P Here's one last problem:
Explanation: Even though stacksToLoot
is a user input, we're only concerned about finding the runtime for n
so stacksToLoot
can be treated like a constant! Therefore, we now have where s = stacksToLoot
which simplifies into n
.
The following two problems are inspired by .
And if you remember your power series, you'll know that this sum is equal to which simplifies into the final answer.
Hey, that looks a lot like the Taylor series for ! Since e
is a constant, it simply reduces to n!
.
Best Case: if the array is nearly sorted except for a couple values. In this case, the while
loop will only run a small number of times, so the only loop left is the for loop.
Worst Case: if the array is totally reversed. This will cause the while
loop to run on the order of O(n)
times, resulting in a nested loop.
Best Case: if n is even. This will result in n being halved every function call.
Worst Case: if n is odd. See the tree below for an illustration of what happens in this case- hopefully the diagram will make it clearer as to why it's O(n).
Best Case: If none of the characters in char[] is 'a', then each call to PNH does work. Total work per layer is always N, with logN layers total.
Worst Case: All of characters in char[] is 'a'. In this case, the for loop recursive calls will dominate the runtime, because it'll be the main part of the recursive tree. The interval start to end is decreased by one in the for loop recursive calls, while that interval is halved in the return statement recursive calls. This means the return statement recursive calls will reach the base case in logn levels, while the recursive calls in the for loop will take n levels. Thus, we can proceed with the same analysis as question 4.
Best Case: if the else if case is always true. This will produce a tree with height n/2, where each height does constant work.
Worst Case: if else if case is never true. Sorry no diagram yet :((