Require some help understanding basic algorithm time complexity

[Linden Garcia]

Hi.

I’m currently trying to get my head around algorithms, specifically time complexity, and failing miserably. I’ve been following a multipart tutorial on algorithms in general, and managed to follow along until it got to discussing time complexity (not Big-O notation yet, simply the concept in more rudimentary terms.

Two of the videos in this series covered the topic in relation to an insertion sort algorithm which sorted an array of 8 numbers. This was the first video:

He explained how long each line — excluding the while loop which would be discussed in the next video — would take to execute. He labelled the time for each line as c1, c2 ... to c8. The first line which starts the loop would take c1 * n, and lines 2, 3, 4 and 8 would run c * n-1.

The confusion for me came in the second video:

This video began to explain the while loop and explore best and worst case time scenarios. Calculating minimum time seemed simple enough: you simply add up each line as it was calculated in the first video. Calculating the worst case was a little more involved but I still understood it: the worst case was dependent on the maximum time the while loop might have to run, so the rest of the equations stayed the same apart from lines 5, 6 and 7, where the equation is c * n * n-1/2.

I followed it right up until the end when I described how you would write the best and worst cases. The best case is apparently an + b, but I have no idea why. He said that n is the size of the array, so that’s the thing that changes (which I understand) but from what I gather, both a and b contain the sum of each line (c1 + c2...etc). I sort of understand why the a would be there, sort of as a container for all each line as it relates to n, but what relevance is b? Do both a and b contain the same thing? And what are we adding together if a is already summing up each line anyway?

The worst case is similarly confusing. a and b are there again, but this time, but this time b is also referencing n and an is squared. I see why it’s squared as that relates to what’s going on with the while loop, but the relevance of the two constants and how they work I don’t understand. The there’s also a c constant, which he didn’t really explain the relevance of at all. The way he wrote the worst case is an squared + bn + c.

Can anyone help me out?

Many thanks!

[Campbell Ritchie]

I haven't got the time to watch those videos. But I looked at Wikipedia, which says that insertion sort is one of the more efficient types of sorting in quadratic time (n²). The bit about quadratic time means that the time taken is proportional to the square of the number of elements; it should take 4× as long to sort a 2,000,000‑element list as a 1,000,000‑element list. Note that is the worst case behaviour; you will occasionally be lucky and find lists requiring little sorting, and the process runs much faster.

[Linden Garcia]

Campbell Ritchie wrote:I haven't got the time to watch those videos. But I looked at Wikipedia, which says that insertion sort is one of the more efficient types of sorting in quadratic time (n²). The bit about quadratic time means that the time taken is proportional to the square of the number of elements; it should take 4× as long to sort a 2,000,000‑element list as a 1,000,000‑element list. Note that is the worst case behaviour; you will occasionally be lucky and find lists requiring little sorting, and the process runs much faster.

Thanks, I’d sort of heard about that but your explanation makes more sense now.

Do you know anything about how the an + b or an squared + bn + c means? As you say it relates to quadratic time, but I have no idea how.

[Campbell Ritchie]

If you mean they calculate the timings with an² + bn + c, then a b c are “constants” and n the number of elements in question. When you are dealign with large numbers, say 1,000,000 or 2,000,000, if you square them you get 1.0×10¹² or 4.0×10¹² and that increase will overwhelm the change from n = 1,000,000 to n = 2,000,000. So the time complexity reduces to its worst (=highest exponent) term. Beware if you have the misfortune to get eⁿ (or xⁿ) complexity (=exponential complexity) where doubling the size of the task can cause its duration to square itself. You will find a naïve recursive approach to calculating Fibonacci numbers in many beginning books; that runs in exponential complexity, but its base is small: it uses (approx) 1.618‟ complexity.

[Linden Garcia]

Campbell Ritchie wrote:If you mean they calculate the timings with an² + bn + c, then a b c are “constants” and n the number of elements in question. When you are dealign with large numbers, say 1,000,000 or 2,000,000, if you square them you get 1.0×10¹² or 4.0×10¹² and that increase will overwhelm the change from n = 1,000,000 to n = 2,000,000. So the time complexity reduces to its worst (=highest exponent) term. Beware if you have the misfortune to get eⁿ (or xⁿ) complexity (=exponential complexity) where doubling the size of the task can cause its duration to square itself. You will find a naïve recursive approach to calculating Fibonacci numbers in many beginning books; that runs in exponential complexity, but its base is small: it uses (approx) 1.618‟ complexity.

So If a, b and c are constants, what are they holding? What does an hold that’s different to bn or c. I guess I’m just not getting how the process of adding up the times for each line of code have been surmised into an squared + bn + c for the worst case, or similarly an + b for the best case.

As you say n relates to the number of elements in question and the squared part represents the growth, but what is the point/function of the constants?

[Paul Clapham]

Linden Garcia wrote:As you say n relates to the number of elements in question and the squared part represents the growth, but what is the point/function of the constants?

At the end of the calculation, there isn't any point. Constant values have no effect on the time complexity. I suppose that the videos put them in because, well like Campbell I didn't watch the videos, but I guess they are intended to show that executing some line of code takes some constant amount of time.

[Campbell Ritchie]

Paul Clapham wrote:. . . there isn't any point. Constant values have no effect on the time complexity. . . .

Complexity goes on the worst component of the formula, and the constants cancel out: an₀² ÷ an₁² reduces to n₀² ÷ n₁².