#timecomplexity

In the last post, we’ve talked about why is it important to understand time complexity of any program.

But wait! What exactly is time complexity? We’ve not talked about that yet.

Time complexity is basically the rate of growth of time taken by a program when the number of input increases. Please Note that time complexity is NOT the time taken by a machine to execute the task, it really depends on which machine is being used, single or multiple processors, available memory etc.

When we talk about time complexity, we basically talk about it’s dependency on the number of inputs.

 Let’s understand it with an intuitive example:

Suppose you’re playing a game with a kid. You’ve put a surprise gift for him in a box but there are 8 similar looking boxes and the kid has to find the gift.

He has tried a box and found it empty, he tried the next and alas! That’s empty too.

How many boxes will he need to open, if he randomly picks a box to find the gift? What do you think?

If he’s lucky, he can find it in the first attempt but in the worst case, he might need to open all 8 boxes to find the gift.

So, time taken by him to get a gift would be proportional to the number of boxes, isn’t it? [More boxes, more time in worst case to find the box with a gift]

Next day, again you played the same game. But this time the boy behaved smartly.

Instead of choosing from the 8 boxes, he divided them into two equal parts and asked you for a hint, if the gift is in one of the boxes on the left or on the right. And based on the answer, he will search. So, he has to find the gift form only four boxes now. He again did the same trick and divided the boxes into two parts and asked you, if the gift is in the left side boxes or right-side boxes. So now, he needs to choose from two only. Again, he repeated the process again & finally found the box with the gift.

So, by doing this kind of search (we can call it binary search where we divide the search space by two in every iteration), the boy found the gift in maximum 3 iteration.

Let me introduce the jargon here.

For n inputs (here n=8), linear search (first approach of the kid) takes time complexity order of n [O(n)] as in the worst case, it takes ‘n’ iteration to search for the desired result.

While for n inputs (here n=8), binary search (second approach of the kid), takes time complexity order of log2n [O(log n)] as in the worst case, it takes ‘log2n’ [Note that: log28 = 3] iteration to search for the desired result.

Don’t worry about the math here!

But what did we learn here is that time complexity talks about rate by which a program execution time increases based on input parameters [we are not considering system’s performance here]

But how do we actually compute time complexity? We will discuss that soon.

 Time for a quick quiz:

What would be the time complexity for the following programs?

1.    def say_hi():

        print(“hi, how are you?”)

     say_hi()

 2.    for i in range(1, n):

        print(“hi, how are you?”)

 Answer to previous quiz: 1_ it iterates ‘n’ times and second loop iterates √n (which is less than ‘n’) times

More new material today with little time to digest yesterday’s! We discussed time complexity of algorithms today. Time complexity (represented mathematically as big O) describes the worst case runtime of an algorithm (independent of external factors such as computer hardware, compiler speed, etc.) in the form of mathematical functions such as ln(n), n^2, and so on. 

The running times in functions in order from fastest to slowest are O(1), O(ln(n)), O(n), O(n*ln(n)), O(n^2), O(2^n), and O(n!). They can typically be determined by dissecting an algorithm or function and determining how many iterations, loops, or operations are occurring. They can also be determined by getting data points on runtime for varying numbers of elements. 

Finally, we ended by doing some cool demos involving running benchmarks for bubble sort and merge sort on 1000, 3000, 4000, and 5000 elements, which showed that bubble sort was really slow (at least for large number of elements as it is pretty fast for smaller numbers of elements). While this lecture was interesting, I found many aspects of it confusing, like average case and amortized time. I guess that’s what I’ll be reading about this weekend! The rest of the day involved writing various functions, determining their time complexities, and then optimizing to decrease big O, including some cool implementations such as a MinMaxStackQueue to keep track of maxs/mins instantaneously in constant time while moving through different numbers instead of having to calculate the maxs/mins during every iteration of different numbers. This was very hard, as we created our own data structures to do this. Again, we barely had time to get to the last step (which still wasn’t working at the time of this writing so another thing to work on during the weekend :/).

Straight from bigocheatsheet.com is this graph below for a more visual depiction of the various big Os discussed in this post.