Identifying Runtime Complexity
Runtime complexity is a term that we use to describe how performance an algorithm is.
We use runtime complexity to compare different solutions to a given problem or different algorithms.
Our goal is to make sure that we have the ability to identifty a given runtime complexity.
How much more processing power/time is require to run your algorithm if we double the inputs?
Some tips right here (in the next image) on some common complexities and how yo can identifiy them:
Big ‘O’ Notation is another way of referencing runtime complexity.
What is the runtime complexity of your solution?
What is the big O of your solution?
They are both asking what is the efficiency of your solution?
In this repository we can see that each problem has several solutions:
Examples of quadratic runtime or N^2.
Two nested for loops iterating over the same collection
In case of two nested for loops iterating over different collections we are talking about O(n*m) nor O(n²).
Another thing we can talk about is the space complexity of an algorithm. So space complexity is extremely similar to performance, but it is a reference to how much RAM or memory or space an algorithm needs to complete a given task. In general, you can really apply a lot of the same rules around runtime complexity to space complexity. Great examples of this would be something like reversing a string, In our case, for every additional character that we added into our input set, we had one additional character that we neede to return in the output set of data. And so the amount of memory that we spent was linear because for every one additional character we needed one additional element in our string to be added.
Another good example of this would be steps algorithm that we also looked at. So in this case, we had said that for each increment of these steps argument, we had to print out to a dish or some number of additional items in our result set. So not only do we have to process more data or we had to iterate through some loop more times, our result set also had significantly more entries inside of it for every record that was added in. And so, this would be a great example of quadratic runtime for space complexity as well, because you can see very clearly right here for 2, we had to producer 4 items, 4 elements in memory. For 3 we nedd 9 elements in memory and for 4 we needed 16 elements in memory.
Space complexity and runtime complexity are not always going to be identical. In many cases , they might be very different.
In the Fibonacci exercise there are 2 solutions. The first is an iterative solution, therefore it is an example of Linear Time: O(n).
The second solution is recursive, a clear example of Exponential Time: O(2^n)
Yes. In the recursive solution, if instead of calculating the result for the value 5 we do it for 6, the number of times the fib(n) function is called grows exponentially.
On the other hand, if you look at the test results, the time used to solve the Fibonacci series of a large number with the recursive function is much higher than if we use the iterative function