Course topic 5 exercises¶

big-O notation¶

For each function, the size of parameter v is N. For each question, always choose the tightest bound.

Question 1

   Mean(Vector v):
     int sum = 0
     FOR elem IN v :
       sum = sum + elem
     END LOOP
     RETURN sum/SIZE(v)

What is the efficiency of Mean()?

O(1)

O(log N)

O(N)

O(N log N)

O( N ²)

Question 2

   MeanOfRange(Vector v, int index1, int index2):
     int sum = 0
     FOR elem IN RANGE FROM index1 TO index2 :
       sum = sum + elem
     END LOOP
     RETURN sum/(index2-index1 +1)

Let index1 and index2 be arbitrary positive integers, such that index1 <= index2. What is the runtime efficiency of MeanOfRange() ?

O(1)

O(log N)

O(N)

O(N log N)

O( N ²)

Question 3

   FindIfOutlier(Vector v, int max_var):
     FOR elem IN v:
       IF max_var > |elem - Mean(v)|:
         RETURN elem
       END
     END
     RETURN "Failure to find outlier"

What is the runtime efficiency of FindIfOutliers()? (The Mean-function was given in the first question.)

O(1)

O(log N)

O(N)

O(N log N)

O( N ²)

Calculating asymptotic efficiency¶

 Mystery1(Array[a1, a2, ... , aN]):
   B := []
   FOR elem IN Array LOOP
     IF first THEN
       B[0] := elem
     ELSEIF elem > LAST(B)
       APPEND(B, elem)
     END IF
   END LOOP
   RETURN  B

Question 1

Assume the APPEND-function runs in constant time. The runtime efficiency of the Mystery1 algorithm is

Always linear, so O(N), Ω(N) ja Θ(N).

O(N), Ω(1) and undefined Θ.

O(N), Ω(1) and Θ(N).

Question 2

If the APPEND-function has a linear O(N) in the worst case, but still runs in constant time on average, how would that affect the efficiency of the whole algorithm?

Nothing would change.

The efficiency in all cases would be multiplied by N.

The worst case would be O(N ²) and Θ would be undefined.

The worst case would be O(N ²), Θ and Ω would stay same.

FindAPair(Array A, Array B):
  FOR a_index IN A LOOP
    FOR b_index IN B LOOP
      IF A[a_index] == B[b_index] THEN
        RETURN (a_index, b_index)
      END IF
    END LOOP
  END LOOP

Question 3

Which of the following give the tightest bounds on the runtime efficiency of the FindAPair-algorithm? Note that you may assume SIZE(A) == SIZE(B).

O(N)

O(N log N)

O(N ²)

Ω(1)

Ω(log N)

Ω(N)

Ω(N log N)

Θ(N)

Θ(N log N)

Θ is undefined.

  Mean(Vector v):
    int sum = 0
    FOR elem IN v :
      sum = sum + elem
    END LOOP
    RETURN sum/SIZE(v)

Question 4

When N is the size of parameter v, what is the efficiency of Mean()? (Choose the tightest bound.)

Ω(1)

Ω(log N)

Ω(N)

Ω(N log N)

Ω( N ²)

  MeanOfRange(Vector v, int index1, int index2):
    int sum = 0
    FOR elem IN RANGE FROM index1 TO index2 :
      sum = sum + elem
    END LOOP
    RETURN sum/(index2-index1 + 1)

Question 5

Let index1 and index2 be arbitrary positive integers, such that index1 <= index2. When N is the size of parameter v, what is the efficiency of MeanOfRange()? (Choose the tightest bound.)

Ω(1)

Ω(log N)

Ω(N)

Ω(N log N)

Ω( N ²)

   FindIfOutlier(Vector v, int max_var):
     FOR elem IN v:
       IF max_var > |elem - Mean(v)|:
         RETURN elem
       END
     END
     RETURN "Failure to find outlier"

Question 6

When N is the size of parameter v, what is the efficiency of FindIfOutlier()? (Choose the tightest bound.)

Ω(1)

Ω(log N)

Ω(N)

Ω(N log N)

Ω( N ²)

RecursiveSum(int N)
  IF N > 1 THEN
    RETURN N + RecursiveSum(N - 1)
  ELSE
    RETURN 1
  END IF

RecursiveSumEveryThird(int N)
  IF N > 1 THEN
    RETURN N + RecursiveSumEveryThird(N - 3)
  ELSE
    RETURN 1
  END IF

Question 7

What is the efficiency of RecursiveSum-algorithm?

O(1)

O(log N)

O(N)

O(N log N)

O( N ²)

Question 8

Which one of the following is true?

Given the same input, RecursiveSum and RecursiveSumEveryThird have the same execution times and they have the same asymptotic efficiency.

Given the same input, RecursiveSum and RecursiveSumEveryThird have different execution times but they have the same asymptotic efficiency

Given the same input, RecursiveSum and RecursiveSumEveryThird have the same execution times, but they have different asymptotic efficiencies.

Given the same input, RecursiveSum and RecursiveSumEveryThird have different execution times and they have different asymptotic efficiencies.

Drilling algorithms & complexities¶

A+ presents the exercise submission form here.