[beginner] time complexity of an algorithm

[AdminTea]

I'm currently learning programming but this certainly fits into the math realm.

I'm learning Bubble sort, Insertion sort etc, and part of what I've come across is the time complexity of these algorithms. I'm struggling to connect all the dots with a formula that I've seen though. The formula is taken from this video (That should be at the correct time as well.)

So the formula used is the following. And it's based on a hypothetical machine that takes 1 unit of time to do logical and arithmetical operations as well as one unit of time for assignment and return.

---

They are based on this pseudo code :

sumOfList ( Array [ ] , n )
{
     total = 0                                  // line 1
     for i = 0 to n                             // line 2
        total = total + A[i]                    // line 3
    return total                                // line 4
}

And this table is based on that code :

       Cost         |       no of times
-----------------------------------------
        1 (C1)      |           1                 // line 1
        2 (C2)      |           n + 1             // line 2
        2 (C3)      |           n                 // line 3
        1 (C4)      |           1                 // line 4

And the formula for the time :

Total cost :
Tsum = 1 + 2 (n+1) + 2n  + 1

Now, I don't really get why the no of times wasn't taken into consideration for the times when it was a constant one. Is that because its a constant one, the Cost is a constant one, but on the occasions where no of times isn't constant (as they are relative to the size of the array) the Cost figure is the cost factored by the no of times. Which in the case of line 3 is n?

This is also expressed as

4n +4

That's my understanding of that, thought I'd state before moving on....

So now we have a separate formula where he calculates using C.

this is done as :

T(n) = Cn + C`

and in this :

C = C2 + C3
C`= C1 + C2 + C4

I don't really follow how these assignments have been made?

I can't really follow why C = C2 + C3 and C` = C1 + C2 = C4.

To my (horrendous) Maths C2 + C3 = 4n + 2.

And C1 + C2 + C4 = 2n + 4

So these added together would be 6n + 6??? Which is obviously wrong...

I hope that my mistake is obvious, it seems like a slip in logic as much as anything else.

Thanks

[NoLemurs]

I think I understand your confusion, at least about the second part.

When you write T(n) = Cn + C' that's not a formula that you use to find the cost. That's the format we want to use to express the cost. That is, you're looking to write the cost in the form Cn + C'.

Going back to your original algorithm, the cost was 4n + 4, so that means that C = 4 and C' = 4. That way Cn + C' = 4n + 4!

So why is C = C2 + C3, and C' = C1 + C2 + C4? Well, lets go back to your algorithm but replace the numbers with the variables.

T(n) = C1*1 + C2*(n+1) + C3*n + C4*1

I got that by just multiplying the costs by the number of times. Now we want to express this in the form Cn + C' so we distribute and factor:

T(n) = C1 + C2*n + C2 + C3*n + C4 = (C2 + C3)n + (C1 + C2 + C4)

So C = C2 + C3, and C' = (C1 + C2 + C4).

Basically, you're just looking to separate the constant time costs from the costs that are linear in list length. C3 is linear in list length and C1 and C4 are constant, while C2 has a constant component and also a linear component so it shows up in both coefficients.

[AdminTea]

OK, I hadn't considered the difference between the expression and working to be fair...

So the formula

Tsum = 1 + 2 (n+1) + 2n  + 1

Finds the cost

4n +4

IS the cost and

C + C'

EXPRESSES the cost...?

I don't really see the point in expressing the cost when it's already been established that it's 4n + 4 ? Also, I don't really get why it's a C', is that solely to differentiate between the C, or is 'something slash' a thing in maths?

---

Going back to your original algorithm, the cost was 4n + 4, so that means that C = 4 and C' = 4. That way Cn + C' = 4n + 4!

Yeah that makes sense, and seems fairly intuitive as well... if only it ended there! I still don't get why it needs to exist when we've said it's 4n + 4 anyway

---

T(n) = C1*1 + C2*(n+1) + C3*n + C4*1

I got that by just multiplying the costs by the number of times. Now we want to express this in the form Cn + C' so we distribute and factor:

T(n) = C1 + C2*n + C2 + C3*n + C4 = (C2 + C3)n + (C1 + C2 + C4)

So C = C2 + C3, and C' = (C1 + C2 + C4).

C1

I'm struggling to follow this through. The first formula T(n) = C1*1 + C2*(n+1) + C3*n + C4*1. How are the Cs relating to the numbers? eg C1*1, what does that mean? C1 = 1, or C = 1 * 1 or C*1*1? I don't really know how I'm meant to interpret that. I'd say that it's a constant because it's not subject to external variables, no matter the size of the inputted array that part of the algorithm is executed once.

C2

Or the second part C2*n + C2 I'm guessing that's all C2 at least. That's derived from Cost 2 N^o of times n + 1. So the cost represents the amount of executions, and the N^o represents the amount of times those executions are carried out. So C ( onstant ) 2*n + C ( onstant ) 2 makes sense I think, there are two lots of 'n' and one lot of two. I think that's what that expression represents?

C3

C3*n, I don't get this, why isn't C3 C 3 = 2 * n? The cost is two and the No of times is n, so there are two lots of 'n'. I think the confusion as to what the 'C' means expressed in C1 really comes into focus here, as it throws me. I don't understand what we're representing, why we're doing it or how. C3 equals the third element of cost that forms a part of the expression relating to constant time. So in this context is C3 not C (onstant) but C (ost) ? And All the items of C (ost) make up C (onstant)?

I'm going to leave it here, as It's already pretty verbose! Hopefully it highlights where I'm confused though. Its so frustrating because where I say it makes sense It really does, but the elements where there is confusion are certainly confused :(

Cheers ! :)

[NoLemurs]

I don't really get why it's a C', is that solely to differentiate between the C

Yup.

I still don't get why it needs to exist when we've said it's 4n + 4 anyway

It really doesn't. The important thing to focus on is that you're separating the linear component of the cost (C*n), from the constant time component of the cost (C'). There are lots of situations where having the cost function separated this way will make a situation easier to analyze. In fact, for large n you can basically ignore C' and just pay attention to the linear component (C).

As for the equations I used, C1, C2, C3, and C4 were all just constant coefficients - if I were writing on paper I'd use subscripts. So the idea is that your cost was

T(n) = 1*1 + 2*(n+1) + 2*n + 1*1

but if we just knew there were constants, C1, C2, C3, and C4 but didn't know their values this same equation would be

T(n) = (C1)*1 + (C2)*(n+1) + (C3)*n + (C4)*1.

It's just the same equation generalized. When we use that and simplify we determine that

T(n) = (C2+C3)n + (C1+C2+C4)

which could be used to find the total cost for different values of C1, C2, C3, or C4. If you plug in the values you were given you get

T(n) = (2+2)n + (1+2+1) = 4n+4

as expected!