Homework 2: Understanding BigO
 Due before class on Wednesday, September 2
For each of the following snippets of code, what is the BigO of the worst case for that algorithm?

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

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

1 2 3 4 5 6
int sum = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { sum++; } }

1 2 3 4 5 6
int sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { sum++; } }

1 2 3 4 5 6
int sum = 0; for (int i = 0; i < n; i++) { for (int j = 5; j < n; j++) { sum++; } }

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

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

1 2 3 4 5 6 7 8
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++; } } }