# IC312: Data Structures (FA16)

Home Policy Calendar Units Assignments Resources

# 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

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.

1. ```int sum = 0;
for (int i = 0; i < n; i++) {
sum++;
}
```
2. ```int sum = 0;
for (int i = 0; i < n*n; i++) {
sum++;
}
```
3. ```int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
sum++;
}
}
```
4. ```int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
sum++;
}
}
```
5. ```int sum = 0;
for (int i = -5; i < n; i++) {
for (int j = -5; j < n; j++) {
sum++;
}
}
```
6. ```int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j*=2) {
sum++;
}
}
```
7. ```int sum = 0;
for (int i = 1; i < n; i*=2) {
for (int j = 1; j < n; j++) {
sum++;
}
}
```
8. ```int sum = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < n*i; j++) {
sum++;
}
}
```
9. ```int sum = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < n/i; j++) {
sum++;
}
}
```
10. ```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++;
}
}
}
```

Created: 2016-09-01 Thu 07:23

Validate