Running time

Describe the running time of the following code in Big-Oh notation in terms of the variable . Show your work to get full credit. This exam is 15% of the final grade.

Write all answers on the space provided below each problem…as was demonstrated during class lectures

1. def foo( k):
   for i in range (k):
   cost = cost + (i * k);
   return cost;
2. for i in range(n+100):
   for j in range(i * n):
   sum = sum + j
   for k in range(n + n + n):
   c[k] = c[k] + sum
   4. for i in range(n * 1000):
      sum = (sum * sum) // (n * i)
      for j in range(i):
      sum = sum + j * i
3. for x in range(n, 0, -1):
   print(“\n\t”, x )
4. for i in range(5):
   for j in range(10):
   print(“\n\t”, j )
5. for i in range(n):
   for j in range(n):
   print(“\n\t “ , j )
6. for i in range(0, 5*n):
   print(“\n\t” , “Hello”)
7. for i in range(n):
   for j in range( n*n):
   print(“\n\t” , “tricky!” )
8. Show the necessary steps to prove the following Notation

Sample Solution