Big O exercises

These exercises should be possible to solve using the two notes:

• The rules of big-O are described in this page
• The useage of logarithms are covered in this page.

Exercise 1

What is the time growth rate (time complexity) of the following method?

public static int count(int[] a, int c)
{
  int count = 0;
  for (int i = 0; i < a.length; i++)
  {
      if (a[i] == c) count++;
  } 
   return count; 
 }

Exercise 2

Suppose an algorithm A takes 5 seconds to handle a dataset of 1000 elements. Fill in the approximate execution time for A depending on the complexity of the algorithm.

Exercise 3

For the following expressions, what is the order of growth (time complexity) of each?

a) n²+ 2n + 1 b) n¹⁰ + 9n⁹ + 20n⁸ + 145n⁷ c) n + (0.001)n³ d) n + log(n)

Exercise 4

Fill out a table where you compare n, log(n), n² and n*log(n)