Homework 2: Understanding Big-O

This is the archived website of IC 312 from the Fall 2014 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

• Due before class on Friday, August 29

For each of the following snippets of code, what is the Big-O of the worst case for that algorithm?

1.  1 2  for (int i = 0; i < n; i++)     sum++;
2.  1 2  for (int i = 0; i < n*n; i++)     sum++;
3.  1 2 3  for (int i = 0; i < n; i++)     for (int j = i; j < n; j++)       sum++;
4.  1 2 3  for (int i = 0; i < n; i++)     for (int j = 0; j < i; j++)       sum++;
5.  1 2 3  for (int i = 0; i < n; i++)     for (int j = 5; j < n; j++)       sum++;
6.  1 2 3  for (int i = 0; i < n; i++)     for (int j = 1; j < n; j*=2)       sum++;
7.  1 2 3  for (int i = 1; i < n; i*=2)     for (int j = 1; j < n; j++)       sum++;
8.  1 2 3 4  for (int i = 1; i < n; i*=2)     for (int j = 1; j < n*n; j++)       for (int k = 0; k < j; k++)         sum++;