Homework 2: Understanding Big-O

• Due before class on Tuesday, September 6

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

1.  1 2 3  sum = 0; for i in range(n):     sum += 1
2.  1 2 3 4 5 6  sum = 0; i = 0 while i < n*n:     sum += 1     i += 1 }
3.  1 2 3 4 5 6  sum = 0; for i in range(n):     j = i     while j < n:         sum += 1         j += 1
4.  1 2 3 4  sum = 0; for i in range(n):     for j in range(i):         sum += 1
5.  1 2 3 4 5 6  sum = 0; for i in range(n):     j = 5     while j < n:         sum += 1         j += 1
6.  1 2 3 4 5 6 7 8  sum = 0; i = 0 while i < n:     j = 1     while j < n:         sum += 1         j *= 2     i += 1
7.  1 2 3 4 5 6 7 8  int sum = 0; i = 1 while i < n:     j = 1     while j < n:         sum += 1         j += 1     i *= 2
8.  1 2 3 4 5 6 7 8 9 10 11  sum = 0; i = 1 while i < n:     j = 1     while j < n*n:         k = 0         while k < j:             sum += 1             k += 1         j += 1     i *= 2