Time complexity analysis – How to calculate running time?

Time complexity analysis – How to calculate running time?

Articles, Blog , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 100 Comments


in this lesson, we will see how to deduce and calculate running time of an algorithm and analyze the time complexity of it the actual time taken by an algorithm or what we also call the running time of the algorithm may depend upon a number of factors and let us see what those factors are, so we will say that running time depends upon factors like whether your machine is a single processor machine or a multiple processor machine and may be also upon which generation of processor you have running time also depends upon what is the read or write speed onto the memory of your machine, so we will say
that read or write speed to memory or disk because your program may have or will surely have a lot of input-output operations running time also depends upon whether
your machine is a thirty two-bit architecture or a 64 bit architecture and it may also depend upon couple of other factors or aspects relating the configuration of the machine on which you’re running your program and last but not least, it also depends upon what input you’re giving to your program or algorithm now when we talk about time complexity analysis of an algorithm we do not bother about all these factors all we bother about is that how our program behaves for various inputs or how the time taken
by the program grows with the input to the program so mostly, we are interested in the rate of growth of time taken with respect to the input now how do we calculate an expression that gives us the rate of growth of time of an algorithm with respect to the input To do so, we first define a model machine where we will execute our program so let’s say be defined a hypothetical model machine with below characteristics it is a single processor machine the architecture of the machine is 32-bit it executes the instructions in the
program sequentially and let us say it takes one unit of time for simple arithmetical and logical
operations like addition subtraction multiplication
division so, 1 unit time for arithmetical and logical operations and it also takes one unit of time assignment to a variable and also one
unit of time to return from a function so one unit for assignment and return and let’s say all other costs are negligible
and we do not account for it now this is a hypothetical model machine
that i have defined and you can define a model machine of your own choice where
you can say that hey, this takes the machine takes this much amount of time for this operation but because eventually we are interested
in calculating a function that gives us the rate of growth of time with respect to input the analysis the analysis will still be the same Now, let us pick up some very simple
examples and try to deduce the functions that define the rate of growth with respect to the input and i will clear this a little bit let’s say we want to write a program to find the sum of two numbers a and b, so i will write a function
here that we take two integers a and b and simply return a + b and i’m only writing a pseudo-code here Now, if i want to go in this particular function using the modal machine then let’s say if the time taken is T and let’s say this is T(sum) then one unit of time for the arithmetic operation, addition and
one unit of time for the return statement so the total time would be equal to 2 units so in this case irrespective of the input
to the program the time taken is exactly 2 units or we can also say that the time taken
is always constant so this particular program is a constant time algorithm now let’s pick up another example let’s say we want to write a program that gives me the some of all the elements in a list so i would write a function sum of list that will take a one-dimensional array A as input and let’s say it also takes as argument to the function the size of the array so the size of the array is n so in this case the program goes like so we start with a variable total and we initialize it to zero and then we run a loop and keep on adding the elements of the array into this particular variable and finally return it after we come out of the loop and before we calculate the time taken, let’s do something here, i will label these statements with line numbers one two three
and four now line one has one assignment so the cost will be one unit and this particular statement will be
executed exactly once line 2 has one comparision which is often there in a loop and since i have written a pseudo-code here only so let’s assume that we have one comparison and one increment and both have cost one unit each and the total cost to execute line 2 is 2 units and this will execute n +1 times one extra time for the false condition when the program actually exits the loop and this also has a cost of two units one for the addition and one for assignment here, so this executes n times and the last line is a simpl return which
executes once and has a cost of one so the total cost let’s say is T(SumOfList) is equal to one plus 2*(n +1) + 2*n +1 and this eventually evaluates to 4n + 4 Now, if this sounds a little messy to mark these absolute terms here in cost we can also write some constants here like the cost of executing Line 1 is say c1 and the cost of executing line 2 can be called c2 and we can go on like
this and then also, we can try to calculate the total cost. So in that case we will arrive at some expression like time taken is a function of n T(n) which is equal to some constant let’s say c times n plus another constant c’ where c is equal to c2+ c3 and c’ is equal to c1 + c2 + c4 but these constants are not so important
because we are interested in the rate of growth of the time taken and in this case, clearly the time taken grows as a linear function simply because it’s proportional to n so for the first example that we had picked we had the time taken to sum up two elements equal to some constant let’s say this
constant was k the second example was where we wanted to have sum of elements in a list and in this case our time taken was a linear function of n, something
like c*n + c’ where c and c’ are some constants if we want to print or calculate the sum of elements in a two dimensional matrix of size n*n, then if you try to deduce the time taken in that particular situation the expression would be something like an^2 + bn + c, where a, b and c are some constants. so you will get ome quadratic equation like this, quadratic
function like this and if we try to plot these three functions on this graph then we get something like this in fact x-aixs here is and should be input size so we can call it, let’s say n clearly, for higher values of n, the rate of growth of the quadratic function is a lot more than the rate of growth of the linear function We often classify these functions in set where the rate of growth of all the
functions in a particular set is very similar for example big-oh of n square will define the set of all the functions of the form an^2 + bn + c similarly all the functions like linear functions like cn + c’ would be defined by O(n), so O(n) is the
the set of all the functions of this particular farm All the functions of the form time equal to some constant belong to the set O(1) and this is the same big -oh
notation that we’re talking about all this while, we
have been talking about all this this classification of functions into these sets is done using the concept of asymptotic bbounds which is a very fundamental concept in time complexity analysis big-oh is actually called an asymptotic notation so this big-h that we often write is called an asymptotic notation and we also have others asymptotic notations like theta and omega and we’ll learn about all of them in the next lesson so thanks for watching

100 thoughts on “Time complexity analysis – How to calculate running time?

Leave a Reply

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