Complexity Analysis

Question 1

Define the Θ-notation

Answer 1

For a given function g(n), we denote by Θ(g(n)) the set of functions

Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) for all n ≥ n0 }

Question 2

What is the difference between the Θ, O and Ω notation?

Answer 2

The Θ notation asymptotically bounds a function from above and below.
The O notation is used when we have only an asymptotic upper bound.
The Ω notation is used when we have only an asymptotic lower bound.

Question 3

Define the O-notation

Answer 3

For a given function g(n), we denote by O(g(n)) the set of functions

O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ c g(n) for all n ≥ n0 }

Question 4

What is the difference between amortized analysis and average-case analysis?

Answer 4

Amortized analysis differs from average-case analysis in that probability is not involved.
An amortized analysis guarantees the average performance of each operation in the worst case

Question 5

Suppose we had an algorithm that took in an array of strings, sorted each string, and then sorted the full array. What would the runtime be?

Answer 5

We cannot just use a single variable like N here for the Big O - Notation, since we have two different values here, the number of elements in the array (‘a’) and the size of the largest string (‘s’).

Sorting each string takes O(s log s) time and we have to do it for each string, so the time for the string comparison is O(a*s log s).
Now we have to sort the whole array. Beware that this is not simply O(a log a), because we need to compare the strings. Each comparison takes O(s) time.

So the final runtime will be O(as log s + sa log a) = O(a*s (log a + log s))

Question 6

What is the runtime of calculating a fibonacci numbers (without memoization)?

Answer 6

O ( 2^n)

Question 7

What is the runtime of calculating a fibonacci numbers (with memoization)?

Answer 7

O (n)