Time complexity analysis - How to calculate running time?

See complete series on time complexity here
In this lesson, we will see how to deduce an expression for running time of a program/algorithm as a function of input size. We define a hypothetical model machine where our algorithm may execute and try to calculate the growth function for running time. Then we classify these functions into broad sets using big-oh or other asymptotic notations.

Pre-requisite: Basic knowledge of programming concepts.

[dragnhuo]

Just like your pointer video, your 11 minutes on time complexity has taught me more than I have learned in a 50 - 75 minute class period. I really appreciate your work. Thanks a ton.

[thecuriousone]

Thank you so much for these videos! I have my exam in Algorithms in a week and your tutorials are waaaay more helpful than my textbook! Thank you sir!

[ORagnar]

Great job! Over seven years ago, but I can still thank you!

[BrandonMcBarrettFace]

Wow... an entire (often unnecessarily complicated) lecture very successfully boiled down to 11 minutes. I'm excited to watch the other videos in your series. Thank you very much for your excellent work!

[brettCU]

Explained better in ten minutes than in 3 hours by my University professor. Thank you.

[lala_minate]

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

[dhwanilshah]

I'll like to point out one mistake here... in the loop for(i=0 ; i<n; i++)
for i=0 -> cost is 1 and it runs 1 time
for i<n -> cost is 1 and it runs n+1 times (1 time for the false condition)
and
for the increment part;
i++ is equivalent to i=i+1;
Therefore, that statement has cost 2,
and it runs for only n times as the increment is done after the loop runs.
So it should be 1 + (n+1) +2n and the rest just like you said.
Hope it was helpful.

[mycodeschool]

HI Malik,

Line 3 is inside the for loop. The loop is running till n. So, it will be executed times for i= 0 to n-1. Line 4 is the for statement that validates (i<n) to decide whether to go inside the body of loop. It will execute one extra time to validate that (i<n) is false and control does not have to go inside the loop now.

[mycodeschool]

Thanks Melchi. Your request is in queue. There are a lot of requests for C beginner lessons and I am creating them first. After that, I will try to get one on threads.

[seetsamolapo]

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!

[georgr]

Thank you so very much for a simple explanation of something very complex. Cheers!

[syntro]

Best programming tutorials!! Very well explained.

[sandykhp]

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.

[CiscoASR]

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

[BM]

Thank you. That was nice and clear... I’m going to suggest others watch this.

[MrEdinaldolaroque]

Thank you for sharing! Valuable information.

[akshayarabolu]

Your lessons are very presented, the logical representations and visuals really make it easy to understand. These videos are by far the best I have found to learn these concepts! Do you have lessons on Hash tables too somewhere??

[mycodeschool]

So, it will be executed n times for i= 0 to n-1.

[melchisalins]

You did an extremely good job in all your videos... Please make a tutorial explaining Threads in C. If possible pthreads. I would like to understand in terms of how a thread is allocated memory in the stack frame.

[flippyflopper]

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?