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

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







    [1]: http://i.stack.imgur.com/eJjea.png
 
 
 
Poll
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.