Exercises

• Order the following functions by growth rate: N, N^1.5, N^2, N logN, N log logN, N log^2 N, N log(N^2), 2/N, 2^N, 2^N/2, 37, N^2 logN, N^3

  2/N, 37, N , N, N log log N, N log N, N log(N 2 ), N log2 N, N 1.5 , N 2 , N 2 log N, N 3 , 2N/2, 2N .
• Suppose T1(N) = O(f(N)) and T2(N) = O(f(N)). Which of the following are true?

  1. T1(N) + T2(N) = O(f(N))
  2. T1(N) – T2(N) = o(f(N))
  3. T1(N)T2(N)=O(1)
  4. T1(N) = O(T2(N))

  1 is true
• sum = 0;

  for( i = 0; i < n; i++ )

  sum++;

  What is the runtime?

  O(N)
• sum = 0;

  for( i = 0; i < n; i++ )

  for( j = 0; j < n; j++ )

  sum++;

  What is the runtime?

  $O(N^2)$
• sum = 0;

  for( i = 0; i < n; i++ )

  for( j = 0; j < n* n; j++ )

  sum++;

  What is the runtime?

  $O(N^3)$
• sum = 0;

  for( i = 0; i < n; i++ )

  for( j = 0; j < i; j++ )

  sum++;

  What is the runtime?

  $O(N^2)$
• sum = 0;

  for( i = 0; i < n; i++ )

  for( j = 0; j < i* i; j++ )

  for( k = 0; k < j; k++ )

  sum++;

  What is the runtime?

  $O(N^5)$
• sum = 0;

  for( i = 1; i < n; i++ )

  for( j = 1; j < i* i; j++ )

  if( j % i == 0 )

  for( k = 0; k < j; k++ )

  sum++;

  What is the runtime?

  $O(N^4)$
• Add two N-digit integers

  O(N)
• Multiply two N-digit integers

  O(N^2)
• Divide two N-digit integers

  Depends on the number of digits, each digit cost O(N)