Big Oh Complexity of the algorithm "for $i=1$ to $z$, for $j = 1-X(i)$ to $Y(i)-n^2$ set $k=0$"

121 Views Asked by At

I've got a past paper algorithm question I'm trying to complete. I was hoping you could helped me, if so great if not then it's fine :P if you can keep in mind ironically (yep cs student) I'm not great at Maths!

Let $X$ be an array with the elements $X(1), \dots, X(n)$ such that each $X(i)$ is an integer in the range $\{1, \dots, n\}$, let $Y$ be an array with the elements $Y(1), \dots, Y(n)$ such that each $Y(i)$ is an integer in the range $\{n^2, n^2+1, \dots, n^3\}$, and let $Z$ be an integer variable with the value in the range $\{1, \dots, n\}$. Then consider the following fragment of code:

for i := 1 to Z do
for j := 1-X(i) to Y(i)-n*n do
k:=0

Analyze the complexity of this code in the best case and worst case.

My Analysis:

$$
    X = [ 1,\ 2, ...,\ n-1,\ n ]\\
    Y = [n^2,\ n^2+1\ ,...,n^3-1,n^3]\\
    Z = [1,2,...,n-1,n]
    $$

For Best case: $$ Z(i) = 1 \\ X(i) = 1\\ Y(i) = n^2\\ $$

for int i := 1 to 1 do
for j:= 1-1 to n^2 - n*n

From here inwards I am stuck and don't know how to find $Big\ O$. Any guidance would be appreciated

For Worst case: $$ X(i) = n\\ Y(i) = n^3\\ Z = n $$

for i:= 1 to N do
for j: = 1-n to n^3 - n^2 
for 0 to n^3 - n^2 
n * n^3 + n * n^2**