HW 2: Understanding Big-O

Solution

You can find the solion here

Overview

This is a written homework assignment. It is due in class, in hard-copy.

Due Date

This homework is due Wednesday, August 31th in class

Grading

The assignment is graded out of 100 points. Each question is worth 10 points.

Submission and Starter Code

Submission must occur in hard copy at the start of class.

Problems

For each of the program-snippets below, what is the big-O of the operation, and provide a brief explanation.

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

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

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

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

int sum = 0;
for (int i = -5; i < n; i++) {
    for (int j = -5; j < n; j++) {
        sum++;
    }
}

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

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

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

int sum = 0;
for (int i = 1; i < n; i++) {
    for (int j = 0; j < i/2; j++) {
        sum++;
    }
}

int sum = 0;
for (int i = 1; i < n; i*=2) {
    for (int j = 1; j < n*n; j++) {
        for (int k = 0; k < j; k++) {
            sum++;
        }
    }
}