The first section, Mathematical Analysis , will contain three formal proofs that

Question

The first section, Mathematical Analysis, will contain three formal proofs that each of the three algorithms have time complexities ?(n^3), ?(n^2) and ?(n), respectively. For each of the three algorithms, first derive a summation that counts the number of basic operations of the algorithm and then determine the order of growth of the summation in terms of the Big Theta ? notation.

The algorithms-

n^3:

int mcss_cubed(int [] array) {
        int max = 0;

        for (int i = 0; i < array.length; i++) {
            for (int j = i; j < array.length; j++) {
                int sum = 0;

                for (int k = i; k <= j; k++)
                    sum += array[k];

                if (sum > max)
                    max = sum;
            }
        }
        return max;
    }

n^2:

    int mcss_squared(int [] array) {
        int max = 0;

        for (int i = 0; i < array.length; i++) {
            int sum = 0;
            for (int j = i; j < array.length; j++) {
                sum += array[j];

                if (sum > max)
                    max = sum;
            }
        }
        return max;
    }

n:

    int mcss_linear(int [] array) {
        int max = 0, sum = 0;

        for (int i = 0; i < array.length; i++) {
            sum += array[i];

            if (sum > max)
                max = sum;
            else if (sum < 0)
                sum = 0;
        }
        return max;
    }

}

Explanation / Answer

// simple

a. for each i, you have j == 0 to array length and for each j you have k == 0 to arraylength. so

i== 0.... arraylength * j == 0 to arraylength * z == 0 to arraylength

i.e In worst case complexity is O(n^3).

now think it as n * n * n = n^3.

now think of n*(n/2) * n = n^3 / 2 even equal to O(n^3) as big O notation is upper bound of all (c *n^3) where c is any constant.

// for more help go throug this

http://openclassroom.stanford.edu/MainFolder/VideoPage.php?course=IntroToAlgorithms&video=CS161L2P8&speed=100

same for n^2 and n removing 1 loop and 2 loops

any further doubt mail me ashishkguptaiit.cse@gmail.com

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.