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