Consider an algorithm with a runtime described by the following function: t(n) =
ID: 3543638 • Letter: C
Question
Consider an algorithm with a runtime described by the following function:
t(n) = 5 minutes + 7n seconds 2 + (p3)n seconds where n is the size of the input.
Find the simplest f(n) such that t(n) 2 O(f(n)).
Consider two algorithms A and B that take time in O(n2) and O(n3), respectively. Is it possible for an implementation of B to be more ecent than an implementation of A in all instances? Show your reasoning.
Explanation / Answer
1. t(n) = 5 * 60 * 10^6 + 7 n^2 + sqrt(3) ^ n microseconds
Hence t(n) = O(sqrt(3)^n) (since exponential function is always greater than polynomial functions), Hence f(n) = (sqrt(3))^n.
2. No, it cannot be efficient for all instances. According to the definition, time taken by A(n>k1) = c1 n^2, for some k1 and c1. Similarly, time taken by B(n>k2) = c2 n^3. Take two cases:
i.) c2>1. Take n = |k1|+|k2|+|c1|. Hence A(n) = c1 (|k1+k2+c1)^2. B(n) = c2 (|k1|+|k2|+|c1|)^3. B(n)/A(n) = c2 (|k1|+|k2|+|c1|)/c1. Since c2 > 1 and |k1|+|k2|+|c1| > c1, hence B(n) / A(n) > 1. So we've found a value of n such that B(n) > A(n).
ii.) If c2<1. Take n = (|k1|+|k2|)c1/c2. Hence n>k1 as well as n>k2, since c1/c2 > 1. Therefore A(n) = (c1^3/c2^2) * (|k1|+|k2|)^2 and B(n) = (c1^3/c2^2) * (|k1|+|k2|)^3. Hence B(n) > A(n).