Join TSR now and get all your revision questions answeredSign up now
    • Thread Starter

    > Let X be an array with the elements X(1), ... , X(n) such that each X(i) is an integer in the range {1,..., n\}, let Y be an array with the elements Y(1), ...., Y(n)$ such that each Y(i) is an integer in the range {n^2, n^2+1, ...., n^3}, and let Z be an integer variable with the value in the range \{1, ...., 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

    > 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
    so i guess that's for 0 to n^1 ??
    n * n^3 + n * n^2**

If you won £30,000, which of these would you spend it on?

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Quick reply
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.