# Time complexity analysis – How to calculate running time?

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
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?”

• ### Karim Post author

Thanks Buddy keep going

• ### Anthony Awuzie Post author

ok am confused from 6:50 how did he get Tsumoflist = 1 + 2(n + 1) + 2n + 1 ??????

I am Growth!

• ### aditya narayan Dixit Post author

One correction I see,
at ~ 6:37 , the cost for line 2 won't be 2(n+1), the initialization will happen only once and n+1 times the increment(2 Units) and comparison(1 unit). So for line 2 total time should be: 1+ 3(n+1).

• ### Edinaldo La-Roque Post author

Thank you for sharing! Valuable information.

• ### CustomPcTech Post author

please explain Cn + C'; where, C = C(1) + C(2) + C(3 and C' = C(1) + C(2) + C(4); How does C and C' represent their respective constants?

• ### Akash Singh Post author

BEST VIDEO EVER SEEN

• ### Akash Singh Post author

thank you sir

• ### Julio Diaz Post author

I was following everything fine until 7:20 when you introduced the constants…you lost me right there!

• ### Hassan Amad Post author

Watching this video was the "A-HA!" moment that I desperately needed to understand time complexity.

Very good!

• ### Hoang Nguyen Post author

I dont get the constant part :/

• ### Shruti Itchapurapu Post author

Thank you so much! Helped me with my exam ðŸ™‚

• ### Pablo Post author

Lost me after the constants…

• ### Srikanth Pb Post author

Excellent videos so far , Please reload a tutorial to elaborate the same tutorial , I am unclear about few things , its on very high level

• ### PRATYUSH SINGH Post author

What do you mean by 'Cost' ?

• ### Ian Cooper Post author

Really a fantastic job on this topic. None of the instructors at my school come close to explaining these concepts like this guy…

• ### RenÃ© Baron Post author

I am now 30 years on large scale enterprise projects. I never had to use such stuff.
Where have you used in real projects and WHY ?

• ### Muhammad Abid Post author

What's that? It's not the way Time complexity is analyzed.

• ### Abdallah Mahran Post author

believe me u r a life saver

• ### Tung Le Post author

in c.n + c' , what does the " c' " mean ??

• ### rajesh dansena Post author

Very precise and clear explanatio. Thanks buddy!

• ### Cameron Fife Post author

Why would we care about low level information such as 32 vs 64 bit, sequential or concurrent execution, or single vs multi processor? I feel like that stuff may speed up performance, but fundamentally shouldn't affect the time complexity of an algorithm.

• ### Akash Sharma Post author

at the point of 6:22 you told the cost for increment and comparison is there but it should be the cost of assignment of i=0 and comparison. Please explain sir

• ### undercurrent Post author

I don't get 5:52.?
The loop only goes from 0 to (n-1)
Therefore shouldn't that "For Line" only be hit (n-1 – 0 + 1) = n times
Eg) if n = 5 then loop goes from 0,1,2,3,4 because 4 = n-1
0,1,2,3,4 is 5 times which is n not (n-1) as noted at 5:52

• ### thefront Post author

What math theories do I need to understand to comprehend what you are teaching so that I may understand O'Notation? I understand Algebra but I'm not sure where or how you're coming up with the formulas at 7:31 and 8:30
Thanks for any insight you can give! ðŸ™‚

• ### emamul mursalin Post author

at 7:58 it should be c' = c1 + c4 (because c2 is variable)

• ### shreyas D Post author

This tutorial is not good as it introduces a jargon for the viewers who are seeing it directly also the example used is a bit complex, the graph is NOT DRAWN AND EXPLAINED PROPERLY.

• ### harshith dega Post author

great effort sir sharing your knowledge dont stop sir

• ### H S Post author

what is worst case of time complexity for

while(n<0)

{
n=n/5
}

• ### Rupinder Kaur Post author

sir can u post one video totally based on all types of sorting real time examples

• ### Flippy Flopper Post author

Definitely much better English than some of the algorithm videos i have watched. I have a japanese lecturer at uni who is really good, but i don't know what he is saying. lol

Cheers from Australia.

P.S. "Algoithm' is pronounced "Al Gore rhythm".
who said white guys don't have rhythm?

• ### Arif Sultan Post author

a very nice methode,,,,, very simple and too much help full ,,,thanx alot for sharing these videos….

• ### Siddharth Post author

Rest In Peace Man. You shall Be Missed

• ### hizzy Post author

Only operations should be counted. Loops should cost zero.

• ### Ishitva Goel Post author

Is this video by Humble Fool ?

• ### r k Post author

very nicely explained. Thank you Sir.

• ### Maham M. Firdous Post author

Is this i<n-1 or i<=n-1?

9:31

• ### Milica Jevremovic Post author

YOU ARE THE BEST!

• ### shobhit sinha Post author

nice tutorial plz use black background in future

• ### Zuher Abud Post author

good intro but this time you messed up in this video you didn't define cost and different cost of each part of a program e.g loops, operations e.t.c do they have different cost or? please clarify
Thank you.

Algordim

• ### Scott123180 Post author

Very good video, thank you

• ### Abdul Wahhab Post author

awsome explaination bro

• ### Zuher Abud Post author

Number your videos please i like to go two or three videos back to understand the present video am watching
Thanks

• ### Ashok Kumar Reddy Kondapati Post author

Thanks for a very brief explanation sir…

• ### dkwroot Post author

Would it be practical to just test the time it takes for an algorithm to complete for a certain number of inputs and then graph it to see if it's linear or not? I mean, if we know the worst case scenario for the algorithm then we should be able to quickly run it a few times and gather some points and then plot it for a good estimate of the time complexity, right?

• ### Dr1nc Post author

love ur videos man, gr8 knowledge and english!

• ### Syntro 126 Post author

Best programming tutorials!! Very well explained.

• ### Syeda Aisha Fatima Post author

you said in above video that 1 times loop will run for false condition so there should be 'n' iterations whether than 'n+1'. may be i am wrong but kindly plz explain this

• ### Madhusudan Sharma Post author

Why didn`t add cost of i=0 in for loop at 7:26 in video, as you have mentioned 1 unit of time for assignment.

• ### Neeraj Agnihotri Post author

Your content is really good and the explanation is damn easy .

• ### Patrascu Lucian Post author

"constant time" -> The time needed for execution remains constant

thanks…

• ### tEch E Post author

just increased the complexity of the video for no reason

al gorthem?

• ### Steve D. Post author

Asymptotic analysis : http://www.thesuperprogrammer.com/2018/02/ds-algorithm-analysis-asymptotic.html

"Algortem"

Perfecto.

• ### Ayush Anand Post author

at 7:42 from where c=c2+c3 came?

• ### BG Musik Post author

Very nicely Explained ..

• ### Fatih Baba Post author

SPECTACULAR!!!!!!!!!!!!!!!! THANK YOU, AT LAST I TOTALLY UNDERSTAND WHATS GOING ON LOOL

• ### blog bot Post author

Most accurate pronunciation of 'behaves' I've ever heard

• ### Ali Haider Post author

Really appreciated your hard work. I read lots of article and books regarding these topics but now i get all the concepts. Your method of explaining is very good. Keep it up

• ### Kaleemullah Khan Post author

sir i need your help to solve my assignment

• ### Vishalchandra Vishal Post author

cant hear what u say man

thnx much

• ### PRANJAL AHLUWALIA Post author

By any chance, you are from GEU?

• ### Himanshu Jotwani Post author

Could anyone tell me why hasn't he considered time take to specify I variable in the loop.. i =0 then i=1 and so on..

• ### Mohan Bhargava Post author

Dude your videos are amazing. Kudos. And I promise i am not trying to be funny , I am being genuine when i say this – your accent is a refreshing breath of fresh air.

• ### POTLURI SAI MOHITH cs14b047 Post author

If the input is an n*n matrix, then the size of the input is O(n^2) and not O(n). So the sum of elements of a matrix is still linear in the size of the input.

Helped alot!

• ### Chemistry Tricks Post author

Very nice explaination…. thanks ðŸ˜ƒ

thank u bro

• ### Chirayu Asati Post author

I want to know how runtime of the program depends whether the processor is 32 bit or 64 bit?

• ### Travis L Post author

Lost me at 00:00

ummm!
Nice

• ### TheJociman Post author

I'm afraid that after completing my computer science studies I will have Indian accent

• ### Derek Xue Post author

very well thanks much

• ### Thiti Mahawannakit Post author

4:08 Tsum ,,,,,, I was like `LOL`

• ### Shrimat Kapoor Post author

I love how he said "behaves" behaaaaves"

hi

• ### Cristina Coslet Post author

You are PERFECTâ˜†

• ### Ritika Pandey Post author

Thank u so much

• ### Azhagi Transliteration Apps - à®…à®´à®•à®¿ Post author

Very good intro. Quite helpful to my son. Thanks a lot.

• ### G NEERAJA Post author

In your videos on Recursion and Sorting algorithms, you didn't consider 1 unit of time for return. You didn't count it in. But in this video, you did. Can you please explain?

• ### pal Post author

At 7:58th sec please check the equation, i think its not matching (the
''C"s equation )…and my 1st question: from interview bit, why did they give directly to algorithms(and suggested to Time complexity as it is in Level 1)… 2nd:Is it basic class of algorithm…3. Is algorithm needed to all?…and dont mind to bother you, please use some advanced teaching board/ can use typing or some other tools, which gives interest to learn and listen.

• ### Sakshi Sood Post author

behaaaaves ðŸ¤ª

amazing

• ### habtamu amsalu Post author

baay'ee namatti tola jabaadhu leencoo ilma oromoo maal sagaleen kee akkas bareedu.

• ### J N Post author

fo the author of this video, this symbol ' is not called dash

• ### Abdullah Sifat Post author

Tsumofmatrix = an^2+bn+c .. how come?

• ### Seetsa Molapo Post author

This is the best explanation EVER on this topic. And I've tried (almost) all the books, sites etc. Hope I can thank you somehow someday sir!

• ### Indra Teja Post author

Just picture Topher Grace as the one giving this lecture. Made it more interesting.

• ### Kamol Nabijonov Post author

I have totally got used to Indian accent. Ignore accent because all good tutorials on internet are made by Indian guys

• ### Ben May Post author

Thank you. That was nice and clear… Iâ€™m going to suggest others watch this.

• ### Anshul Agrawal Post author

on generation how ?