SUNY Geneseo Department of Computer Science

Problem Set 10 -- Analysis of Loops

CSci 240, Spring 2007

Prof. Doug Baldwin

Due Wednesday, March 21

Purpose

The purpose of this exercise is to increase your ability to derive formulas for the number of operations that loops execute.

Background

This exercise draws on material from section 9.1 of our textbook. This material was also discussed in the March 5 and March 19 lectures.

Exercise

Derive expressions for the number of multiplication operations each of the following iterative algorithms executes, in terms of n.

Algorithm 1

    for ( int i = 0; i < n; i++ ) {
        sum = sum + i * i;
    }

Algorithm 2

    for ( int i = 0; i < n; i++ ) {
        for ( int j = 0; j < n; j++ ) {
            table[i][j] = i * j;
        }
    }

Algorithm 3

    for ( int i = 0; i < n; i++ ) {
        for ( int j = 0; j < i; j++ ) {
            table[i][j] = i * j;
        }
    }

Algorithm 4

    for ( int i = 0; i < n; i++ ) {
        for ( int j = 0; j < i; j++ ) {
            totalProd = totalProd * i * j;
        }
    }

Algorithm 5

    for ( int i = 0; i < n; i++ ) {
        int limit = i * n;
        for ( int j = 0; j < n; j++ ) {
            for ( int k = 0; k < limit; k++ ) {
                System.out.println( j * k );
            }
        }
    }

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office. Please bring written written derivations for ach algorithm to the meeting.