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..

 

[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

 

[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

 

[Una]

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

 

[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.