Complexity of Algorithms

[Alex]

hey just need a quick response, studying for finals...

here is a small chunk of pseudocode and the complexity is calculated on each line...

now i just dont get how individual lines add to the total in the way that is expressed by it...

and i really dont get how the total was obtained... can someone walk me through line by line pleeeeease? 🙂

thx !!

 

[Alex]

bump please?

 

[gopunk]

first line, one op for accessing value of array, one for assigning to currentMax
loop, i'm not sure where the 2+n comes from
loop content, 2(n-1) for each line because each step takes 2 ops and it (the loop) is done n-1 times

etc

i don't think that's really important tho, all you need to know is that the only thing dependant on the input is a loop whose body only does constant time operations, which means the algorithm is O(n)

 

[Alex]

Originally posted by: gopunk
first line, one op for accessing value of array, one for assigning to currentMax
loop, i'm not sure where the 2+n comes from
loop content, 2(n-1) for each line because each step takes 2 ops and it (the loop) is done n-1 times

etc

i don't think that's really important tho, all you need to know is that the only thing dependant on the input is a loop whose body only does constant time operations, which means the algorithm is O(n)

thanks that kinda helps, but we get chucks of code link this and are expected to do the same as the example 🙁

 

[Alex]

anyone else wanna give this a shot?

 

[Ameesh]

what part are you having problems with?

 

[Alex]

Originally posted by: Ameesh
what part are you having problems with?

i dont get the 2 + n line

and also why is the total 7n-1 ?

 

[sandmanwake]

currentMax<--A[0].
One operation to access A[0], one to assign it to currentMax. Count=2.

For loop
One operation to assign i a value of 1 initially. One to determine what n-1 is, afterwards, I assume it's in cache and doesn't have to be determined any more. Count so far, 2. There are n comparisions in the for loop, therefore count=2+n.

if A>currentMax.
n-1 times through the loop. However, one operation to access A and one to determine if A is > currentMax. I think currentMax is still in cache, so you don't have to access it from memory again. Therefore count=2(n-1).

currentMax<--A
One to access A, one to assign it to currentMax. When you get to the if statement above, currentMax still hadn't changed, so it's still in cache. Therefore, count = 2(n-1). 2 operations * (n-1) times through the loop.

increment i
See it as i=i+1. Once to add 1 to i and once to assign that value back to i. No need to access old value of i since it's still in cache. You do it n-1 times. Therefore, 2(n-1).

return currentMax.
count is just 1.

As to how the total is 7n-1, just do the math, it works out. Add up all the operations.

 

[alkemyst]

the total is just addition.

2
2+n

2(n-1) = 2n-2 so:

2n-2
2n-2
2n-2
1

2+2+n+2n-2+2n-2+2n-2+2n-2+1
2+2-2-2-2+1 = -1
n+2n+2n+2n = 7n

7n-1

With a do loop you must do it once always and once for it's last iteration/failure + n number of iterations.

 

[Alex]

whoa awesome thanks!
ive moved onto economics now... both finals tomorrow... but i will read this in more detail when i get back to programming 🙂