CSE 431: Asymptotic Notation Practice Quiz

1. Consider the following pseudocode function operating on an unsorted array (A) of size n:
  function_a(A):
      if (len(A) <= 2) return a[0]
      for element in A:
          if element > 3:
              return element
      return function_a(A[1:])
Which of the following recurrence relationships might you use to identify the worst-case running time for this algorithm? (Note: 'c' is an arbitrary constant in each option)

2. If an algorithm has a O(n) worst-case time, will it have a O(n²) average-case time? (Hint: Consider the difference between O, Θ, and Ω)

3. Given the following pseudo code, what is the worst-case big-Θ time complexity in terms of n?
  z = 1
  for i = 1 to n
      for j = 1 to n
             z += i + j
  for i = n to 1
      for j = n to 1
             z += j + i
  for i = 1 to n
      for j = 1 to 5
          for k = 1 to 10
             z += i + j + k

4. Which of the following describes the comparison between the functions 9n3 and 3n?

5. Given that:
   `f(n) = 3n*log(n), if n is even, or
           5log(n), if n is odd`
   `g(n) = 6n3`
Which of the following describes the comparison between f(n) and g(n)?

6. Given the following pseudo code, what is the worst-case big-Θ time complexity of my_function(n) in terms of n?
  my_function(n, c):
      x = 0
      for i in range(n):
          x += i * c
      if (n > 3) return my_function(n - 1) + x
      else return x

7. Given the following recursive function, how fast does f(n) grow with n? (Note: we are NOT asking about the time to compute the function, we are asking which of the following functions is a big-Θ bound on f(n))
  f(n) =
      0, if n < 4
      f( floor(n/2) ) + n, otherwise

8. Given that:
   `f(n) = 7n, if n is even, or
           3n, if n is odd`
   `g(n) = 10n*log(n)`
Which of the following describes the comparison between f(n) and g(n)?

9. Given the following recursive function, how fast does f(n) grow with n? (Note: we are NOT asking about the time to compute the function, we are asking which of the following functions is a big-Θ bound on f(n))
  f(n) =
      10, if n < 2
      f(n - 1) + 5, otherwise

10. Given the following pseudo code, what is the worst-case big-Θ time complexity in terms of n?
  z = 1
  for i = 1 to n
      for j = i to 10
             z += i + j