1
$\begingroup$

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** 
$\endgroup$

marked as duplicate by Raphael Jan 3 '15 at 0:43

This question was marked as an exact duplicate of an existing question.

  • $\begingroup$ Reposting the same question is not how you should approach this. Try to apply the method from the reference post (or any method, really) and explain where you get stuck. Failing that, try to formulate a specific question about the reference post resp. what you don't understand. (Remember that you simply won't be able to do algorithm analysis without understanding general techniques for analysing loops such as these here, so you should eventually understand at least some of the reference post. So it's not a detour, it's your way to success.) $\endgroup$ – Raphael Jan 3 '15 at 0:46

Browse other questions tagged or ask your own question.