# Time Complexity (under construction) ([home](https://github.com/alexhkurz/introduction-to-programming/blob/master/README.md) ... [previous](https://hackmd.io/@alexhkurz/Hkc7HoSC8) ... [next](https://hackmd.io/@alexhkurz/r1erdGSlP) ... ) Under the name of Time Complexity, we understand the study of how long it takes for an algorithm terminate, expressed as a function of the size of the input. Actually we are not usually interested in the precise function, as it would depend on the hardware and the operating system and possibly other factors. Rather, for example, we say that an algorithm is linear (or more precisely, has linear time complexity), if doubling the input size means that the run time does not more than double. Similarly, we speak of logarithmic or quadratic or cubic or exponential time complexity, for example. **Activity:** Can we guess the time complexity of the following problems/algorithms? - Finding whether the ace of spades is an unsorted deck of cards. - Finding whether the ace of spades is in a sorted deck of cards. - Finding a word in a dictionary. - Sorting a collection of words alphabetically. - ... We discussed the time complexity of a simple [sorting algorithm](https://hackmd.io/@alexhkurz/r1erdGSlP) in some detail. Time complexity is closely related to one of the most important questions your boss may ask you, namely whether your solution to a software engineering problem scales. What does that mean? **Activity:** Compare the [iterative](https://github.com/alexhkurz/introduction-to-programming/blob/master/src/iterative_fib.py) and the [recursive](https://github.com/alexhkurz/introduction-to-programming/blob/master/src/recursive_fib.py) implementation of the Fibonacci sequence for inputs $n=10,20,...$. What is the largest value of $n$ for which you can compute $fib(n)$ with either of the two programs? What is going on here? We could answer this question with a theoretical pen-and-paper analysis alone. But it is also useful to first run some experiments to get a better feel for the sitatuation. We can amend the programs so that, apart from only computing $fib(n)$, they also keep track of the resources they use. For example, **Activity:** Insert a (global) variable `count` in [recursive_fib.py](https://github.com/alexhkurz/introduction-to-programming/blob/master/src/recursion_fib.py) that counts how often `fib` is called. - Make a table showing `count` as a function of the input `n`. - Can you find a formula that expresses `count` depending on `n`? Another kind of experiment we can run is to actually measure the real time that programs are taking. **Activity:** Download [gnomon](https://github.com/paypal/gnomon#installation) and use it to measure the time that the computation of `fib(n)` takes: - Make tables showing the total time as a function of the input `n` for both [iterative](https://github.com/alexhkurz/introduction-to-programming/blob/master/src/iteration_fib.py) and the [recursive](https://github.com/alexhkurz/introduction-to-programming/blob/master/src/recursion_fib.py) - For [recursive](https://github.com/alexhkurz/introduction-to-programming/blob/master/src/recursion_fib.py), how well does `count` correlate with the total time? ## References - [Stackoverflow: Using global variables in a function](https://stackoverflow.com/questions/423379/using-global-variables-in-a-function)