# 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

KarimPost authorThanks Buddy keep going

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

napischuPost authorI am Growth!

aditya narayan DixitPost authorOne 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-RoquePost authorThank you for sharing! Valuable information.

CustomPcTechPost authorplease 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 SinghPost authorBEST VIDEO EVER SEEN

Akash SinghPost authorthank you sir

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

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

QbabxtraPost authorVery good!

Hoang NguyenPost authorI dont get the constant part :/

Shruti ItchapurapuPost authorThank you so much! Helped me with my exam ðŸ™‚

PabloPost authorLost me after the constants…

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

PRATYUSH SINGHPost authorWhat do you mean by 'Cost' ?

CHOWDHURY M. SAMSUJJOHAPost authorsir i want the tutorial on algorithm course!please help!

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

RenÃ© BaronPost authorI 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 AbidPost authorWhat's that? It's not the way Time complexity is analyzed.

Abdallah MahranPost authorbelieve me u r a life saver

Tung LePost authorin c.n + c' , what does the " c' " mean ??

rajesh dansenaPost authorVery precise and clear explanatio. Thanks buddy!

Cameron FifePost authorWhy 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 SharmaPost authorat 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

undercurrentPost authorI 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

thefrontPost authorWhat 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 mursalinPost authorat 7:58 it should be c' = c1 + c4 (because c2 is variable)

shreyas DPost authorThis 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 degaPost authorgreat effort sir sharing your knowledge dont stop sir

H SPost authorwhat is worst case of time complexity for

while(n<0)

{

n=n/5

}

Rupinder KaurPost authorsir can u post one video totally based on all types of sorting real time examples

Flippy FlopperPost authorDefinitely 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 SultanPost authora very nice methode,,,,, very simple and too much help full ,,,thanx alot for sharing these videos….

SiddharthPost authorRest In Peace Man. You shall Be Missed

hizzyPost authorOnly operations should be counted. Loops should cost zero.

Ishitva GoelPost authorIs this video by Humble Fool ?

r kPost authorvery nicely explained. Thank you Sir.

Maham M. FirdousPost authorIs this i<n-1 or i<=n-1?

midenokPost author9:31

Milica JevremovicPost authorYOU ARE THE BEST!

shobhit sinhaPost authornice tutorial plz use black background in future

Zuher AbudPost authorgood 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.

Firas El JerdyPost authorAlgordim

Scott123180Post authorVery good video, thank you

Abdul WahhabPost authorawsome explaination bro

Zuher AbudPost authorNumber your videos please i like to go two or three videos back to understand the present video am watching

Thanks

Ashok Kumar Reddy KondapatiPost authorThanks for a very brief explanation sir…

dkwrootPost authorWould 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?

Dr1ncPost authorlove ur videos man, gr8 knowledge and english!

Santosh KumarPost author1.25x your welecome

Syntro 126Post authorBest programming tutorials!! Very well explained.

Syeda Aisha FatimaPost authoryou 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 SharmaPost authorWhy 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 AgnihotriPost authorYour content is really good and the explanation is damn easy .

Patrascu LucianPost author"constant time" -> The time needed for execution remains constant

tapanjeet royPost authorthanks…

tEch EPost authorjust increased the complexity of the video for no reason

Marcus AsethPost authoral gorthem?

Steve D.Post authorAsymptotic analysis : http://www.thesuperprogrammer.com/2018/02/ds-algorithm-analysis-asymptotic.html

Ferkst KjÃ¸ttPost author"Algortem"

Jiaqi YangPost authorPerfecto.

Ayush AnandPost authorat 7:42 from where c=c2+c3 came?

BG MusikPost authorVery nicely Explained ..

Fatih BabaPost authorSPECTACULAR!!!!!!!!!!!!!!!! THANK YOU, AT LAST I TOTALLY UNDERSTAND WHATS GOING ON LOOL

blog botPost authorMost accurate pronunciation of 'behaves' I've ever heard

Ali HaiderPost authorReally 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 KhanPost authorsir i need your help to solve my assignment

Vishalchandra VishalPost authorcant hear what u say man

Asaduzzman masumPost authorthnx much

PRANJAL AHLUWALIAPost authorBy any chance, you are from GEU?

Himanshu JotwaniPost authorCould 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 BhargavaPost authorDude 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 cs14b047Post authorIf 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.

Suyash YadavPost authorHelped alot!

Chemistry TricksPost authorVery nice explaination…. thanks ðŸ˜ƒ

Usama Iftikhar ButtPost authorthank u bro

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

Travis LPost authorLost me at 00:00

M S NITISH CHANDRAPost authorummm!

Nice

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

Derek XuePost authorvery well thanks much

Thiti MahawannakitPost author4:08 Tsum ,,,,,, I was like `LOL`

Shrimat KapoorPost authorI love how he said "behaves" behaaaaves"

Will PIPost authorhi

Cristina CosletPost authorYou are PERFECTâ˜†

Ritika PandeyPost authorThank u so much

Azhagi Transliteration Apps - à®…à®´à®•à®¿Post authorVery good intro. Quite helpful to my son. Thanks a lot.

G NEERAJAPost authorIn 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?

palPost authorAt 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 SoodPost authorbehaaaaves ðŸ¤ª

Mayank tiwariPost authoramazing

habtamu amsaluPost authorbaay'ee namatti tola jabaadhu leencoo ilma oromoo maal sagaleen kee akkas bareedu.

J NPost authorfo the author of this video, this symbol ' is not called dash

Abdullah SifatPost authorTsumofmatrix = an^2+bn+c .. how come?

Seetsa MolapoPost authorThis 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 TejaPost authorJust picture Topher Grace as the one giving this lecture. Made it more interesting.

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

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

Anshul AgrawalPost authoron generation how ?