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

1 2 3
sum = 0; for i in range(n): sum += 1

1 2 3 4 5 6
sum = 0; i = 0 while i < n*n: sum += 1 i += 1 }

1 2 3 4 5 6
sum = 0; for i in range(n): j = i while j < n: sum += 1 j += 1

1 2 3 4
sum = 0; for i in range(n): for j in range(i): sum += 1

1 2 3 4 5 6
sum = 0; for i in range(n): j = 5 while j < n: sum += 1 j += 1

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

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

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