In-Depth Post #4

Since my last blog post, I feel like I haven’t done as much as I usually do in this amount of time because I’m having a bit of trouble with the recursive algorithm for my calculator.

Calculator Update

Last week, I talked about how I will be re-working my calculator to use recursion instead of iteration. The main reason for this is that the recursion, in most cases, will be more efficient (in terms of runtime, the computer will be able to run the program faster).

The reason my previous solution was so bad is because it made use of three loops nested inside each other, which had a Big O time complexity of O(n ^ 3) in the worst case scenario. This just means that the amount of operations that need to be calculated by the computer is the number of operations that the user inputs cubed. For example, if the user inputs 1+2+3+4+5+6, the computer will have to use 125 operations to calculate the answer, as there are five plus operators, and 5 ^ 3 = 125. This is actually really bad and scales extremely poorly. Just think about if the user inputted 1000 operations! Of course, this is the worst case scenario and in reality the time complexity will be a little bit better, but it’s still extremely bad even if not the worst case scenario.

The new recursive solution that I am working on has a time complexit of O(n), so the amount of operations the computer calculates is directly proportional to the amonut of operations the user inputs.

Here’s a side by side comparison of the two solutions.

As you can see, the new solution is linear, whereas the old solution is cubic.  The cubic graph practically goes straight up as the user inputs more operators, so the new solution is a massive improvement over the previous one, especially if the user inputs a particularly large amount of operators.

This is all great, except for the fact that recursion is much harder than I expected it to be. Because of the nature of recursion and its compactness, I find it really hard to think about because you can’t think about it step by step. Instead, you have to just trust that your own code is correct. This also makes it really hard to debug and find problems in your code when you find a bug that you need to fix. Nonetheless, I do really like the challenge and I find it very interesting!

How to have a beautiful mind

Here my mentor and I were talking about a possible recursive algorithm that would definitely be much more efficient than an iterative solution if the user inputted a large amount of operations. However, when my Steven was talking, I made an interesting observation, and afterwards I asked the question, “How would the recursive algorithm compare to the old iterative algorithm if the user only inputted one operator.” This was actually really interesting because since there is only one operator and the time complexity of the old solution was O(n^3), 1^3 is still 1, and therefore, it should be the same as the recursive algorithm. There was one I noticed that we didn’t consider, though – Doesn’t calling a method require an operation, because it has to push it onto the stack?”

The reason for this actually has to do with the way that methods are implemented, and the reason we didn’t notice it earlier was because normally, when calculating time complexity, you only really take into account comparing and changing values – And it turns out, there’s a reason for this: After a bit of Googling, we found out that the compiler does something called “inlining” the code. How this works is when the program is being compiled (so actually before the program is being run), the block of code within the method will replace the statement calling the method. This makes sure all the method logic isn’t done while the program is running, which would slow down the program. So, the conclusion was: In most cases, the runtime of calling functions is quite negligible as the compiler usually will do that before the program runs, and the calling of the method does not require an operation.

 

Thanks for reading!

Posted in Uncategorized.

Leave a Reply

Your email address will not be published. Required fields are marked *