This question is an exact duplicate of:
I have asked this question before and the question was closed. Due to it being a duplicate with algorithm analysis. I've looked at this thread that I'm constantly reminded of but I do not understand it in my scenario. I've gotten near the end of a past paper question and I'd just like to know where I can go from here to work out the big Oh from what I've done so far.
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**
