What do we mean by Time Complexity?
I am assuming that the person who is reading this blog is just like me who always freaks out whenever it comes on understanding Data Structures and Algorithms. Don't worry mate, in this blog we are going to figure out together how to deal this "Problem".
Let's understand how a computer programming algorithm works. We can compare a computer(any computing machine) with a human brain. In our day to day life our brain follows multiple sequential commands to accomplish a particular task. Just like that a computer follows the sets of instructions we as a computer programmers give to it to perform any task. The set of instructions/steps a computer follows to accomplish a task is called Algorithm. A computer takes time to execute every programmig algorithm. But the time requirement for every algorithm is not the same. Different algorithms take different amount of time to get executed(just like making tea and doing your assignment requires you different amount of times). On the other hand the execution time of an algorithm varies with the input size(the amount of material we work with). For example: The time you’ll need/spend to make tea for ten people will be more than the time you’ll need to make one cup of tea,because you’ll need more water/milk for ten cups of tea than a single cup of tea and more amount of water/milk requires more time and heat to boil. Just like this when you write an algorithm of finding sum of "n"(n is a variable which can be any positive integer)numbers the time to execute this algorithm for two numbers will be less than the time required for 100 numbers.
Again, when we are talking about efficiency of performing a task we can not forget to consider the capability of the performer. For example: Your mother takes less time to make tea than you spend to make(as you need to find everything and end up making a mess in the kitchen 😐). This is because your mother is more efficient in executing the tea making process but you are a confused kiddo! Just like this different devices take different amount of times to execute a program.
The time variation of an algorithm due to the changing input size is called "Time Complexity of an Algorithm".
How do we measure Time Complexity of an Algorithm
As we have already discussed that the execution time of a computer program very easy with the input size as well as the device we run the program on. So it will not be appropriate for us two measure the absolute valuevalue of the execution time. So the mathematicians have come up with the idea of expressing the execution time as a relationship between the input size and time.
This relationship is expressed using different equations for different types of algorithms.The relationship between the input size and the time required can be linear or nonlinear. For example if we loop through a list Data structure using a single loop then the relationship between the input size and execution time can be expressed like a linear funtion.
There are three cases(we will consider these three) of time complexity. These three cases are expressed with three notations which are called the Asymptotic Notations. When the program works with the minimum input size possible and takes minimum possible time to be executed we call it the Best case time complexity and it is expressed with Big Omega(Ω(n))notation. When our program has to work with the maximum possible input size it requires maximum time to execute this case is the Worst case time complexity and it is expressed with Big O (O(n)) notation. The Average case time complexity is the average of Big O and Big Omega complexity which is expressed with Big Theta(θ(n)) notation.
Often a programming problem is solved using multiple algorithms
but not every algorithm is time efficient. When we talk about time efficiency of a computer program we actually compare the worst case time complexity which means we consider Big O.
Big O or the worst case time complexity expression comes from the relationship of time and input size we talked about.
Top comments (0)