Algorithm Complexity Analysis

[Una]

Just looking over some past paper and I got a question I seem to be struggling on

Let Z be an array with elements Z(1), Z(2),...,Z(n) such that each Z(i) is an integer in the range {1,2,...,(n^2)-1,n^2}. Let W be an array with elements W(1), W(2),...,W(n) such that each W(i) is in the range {n,n+1,...,(n^3)-1,n^3}.
Then consider the following fragment of code:

k := 0
for i := 1 to n do
   for j := Z(i)*W(i) to n*n do
      k := k+1

Analyse the complexity of this code for the best and worst case, counting 1 unit for each basic operation, and expressing the total count as function of n.

Now I think I the best case would be when N = 1. I.e W and Z have 1 as one element (both of value 1). Thus,
k := 0 num execs = 1
for i := 1 to n do number execs = n+1
for j := Z(i)*W(i) to n*n do number of execs = 2
k := k +1 number of execs = 1

O = 1 + (n+1) + 2 + 1
= O(n)

However in the case of the worst case I am currently feeling retarded
I think the worst case would be when Z(i ) = 1, W(i ) = n, so 1*n.

Now I can tell by looking at it that the code should be O(n^2) but im not sure how to come up with this in the worst case. Can anyone help?

 

[Una]

Nevermind think I solved it for worst case now,

Basic Op                               Number of Executions
k := 1                                   1
for i := 1 to n do                       n+1
for j := Z(i)*W(i) to n*n              n^2 + n
k := k + 1                             n^2

So 1 + (n+1) + (n^2+n) + n^2
= n^2
= O(n^2) worse case

I think thats right..

 

[Spuds]

Best case should be when both Z and W have 1 element which give the algorithm a complexity of order n.

Worst case is when both arrays have n elements which will give you a complexity of (n^2)^n Inner loop is run n*n times which gives you (n^2) while the outer loop runs n times, each time runing the inner loop again

 

[Una]

Best case should be when both Z and W have 1 element which give the algorithm a complexity of order n.

Worst case is when both arrays have n elements which will give you a complexity of (n^2)^n Inner loop is run n*n times which gives you (n^2) while the outer loop runs n times, each time runing the inner loop again

Hmm ok yep I get it now, thanks

 

[|Ric|]

I understand this question differently:
Best case, Z(i) >= n for all i, W(i) > n for all i
Now the inner loop never runs so the complexity is O(n)

Worst case is Z(i) = 1 for all i, W(i) = n for all i
Now the outer loop runs O(n) times, the inner loop O(n^2 - n) = O(n^2) times
So total is O(n^3)

I haven't done this stuff in much detail yet but that is my understanding of the question

 

[|Ric|]

The approach of changing the value of n is wrong because it wants the complexity as a function of n, i.e. given this code and a value for n you can give a bound on the number of operations.
Saying well if n is 1 then it does so and so is wrong, what if n is 0?

 

[Una]

Yeah (n^2)^n is n^3 the way you have answered it is slightly different but comes up with the same results. We are ment to do detailed analysis though so you got to consider the checking of the control part of the loop as well even if the body is not executed even though this won't make any difference to the O notation usually. I think you mean O(n^2) + n = O(n^2) for the inner loop though. The weirdness of the pseudocode also means for i := 1 to 1 do actually means it will execute the body once and the check afterwards.

Ah yeah.. I get what you mean about changing the value of N. Though it can't be 0 though mind considering you can't have 0 length arrays

 

[|Ric|]

Um (n^2)^n != n^3
Think you are have a blonde moment

(3^2)^3 = 723
3^3 = 27

 

[Una]

Haha fs indeed Time to take a break me thinks...

 

[|Ric|]

Lemme explain this again

Best Case is when Z is full of n's and W is full of something greater than n
Now Z(i)*W(i) is greater than n*n so the inner loop never gets executed.

We go around the outer loop n times and every time round we check the bounds of the inner loop. This may take 4 operations in total so it would give a complexity of O(4n) but this equals O(n) because there is already an implicit constant so we just lose the 4 into it.


Now the worst case, the most executions of the outer loop is when we go from 1 to n*n. But the smallest possible value of Z(i)*W(i) is n because we can fill Z with 1's and W with n's.
So for each time around the outer loop we will do the inner loop from n to n*n, i.e. (n^2 - n) times. Hence the complexity O(n^2 - n), but we can lose the n because n^2 dominates and get O(n^2)
So the inner loop is O(n^2) and the outer loop O(n), i.e. we are going to do n^2 things, n times, i.e. n^3 operations

Hope that helps, I can't see any basis for your method to work, think its just coincidence it can be fudged to the same answer

Sorry if I am just dragging this out because I am fully prepared to admit this is one area I don't fully understand but I'm fairly certain this is correct and the way you should think about it.

 

[Una]

No you are correct I was well off with my method at the start and just reading through your explanation makes sense now that you are right. Never really understood this well first time round and only started revising today.. seems I got a bit to cover Thanks for the clear explanation.