2

I'm revising for an exam entitled "Algorithms and Scientific Computing" and have little idea about how to do this question, it's from a past exam paper. I know an algorithm with O(3^n) complexity triples in complexity with each new element added and an algorithm with O(n^3) complexity grows proportional to the cube of n, but I don't know how to use that information to answer the question. Here is the question, I would hugely appreciate any help given. Thanks.

Algorithms A1 and A2 are stated to have complexities On^3and O3^nrespectively. On an input of size n = 10,000 both algorithms run in exactly the same time t = 10 seconds. How much time do you expect each algorithm to take on an input of size i. n = 9,990 ii. n = 30,000

JavaChick2570
  • 15
  • 1
  • 2
  • 1
    Big-O notation describes the *limit* of complexity as `n` approaches infinity. For small enough `n` there are usually other factors that need to be considered for an exact run time. In your case you are probably expected to ignore those other factors, but others might not be so lucky. – Mark Ransom Apr 19 '17 at 14:30
  • 1
    Possible duplicate of [What is a plain English explanation of "Big O" notation?](http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) – Paul Hankin Apr 19 '17 at 15:55

2 Answers2

4

If we were being pedantic, we could say that the problem is under-specified.

When it is stated that an algorithm is in the O(f(n)) class, it means that there exist a k such that its run time is upper bounded by k · f(n). We are only given the execution time for a single n value, which does not offer much constraints, in practice both algorithms could be in O(1) (which is a subset of the O(3n) and O(n3) classes of functions), so a valid answer would be that both algorithms always run in a constant time of 10 seconds.

This is probably the reason why the problem may appear more difficult than it actually is. Otherwise, by making some standard assumptions, as it is shown in the next part of the answer, it becomes straightforward.

In practice, when one specifies the complexity class of an algorithm, the intention is for the bounds provided to be as tight as possible. This is what we should assume here, to make this problem well-defined.

So we will assume that the run times of the two algorithms are like this:

time1(n) ~= k1 · n3

time2(n) ~= k2 · 3n

Using the provided information we can find k1 and k2.

10 = time1(10000) = k1 · 100003 => k1 = 10 / 1012 = 10-11

10 = time2(10000) = k2 · 310000 => k2 = 10 / 310000

Using these values for k1 and k2 we can compute the time for any other n values, by substituting them in the formulas for time1(n) and time2(n).

danbanica
  • 3,018
  • 9
  • 22
  • Be careful with complexity: it's easy to put down an ugly *counter example* `t = 1e-100 * n**3 + 10`. The algorithm has `O(n**3)` complexity and time `t = 10` when `n = 10000`. However, `t = 10` (the same) for `n = 9990` as well as `n = 30000`... – Dmitry Bychenko Apr 19 '17 at 14:47
  • 2
    indeed, but exactly that is the point of the first part of my answer -- without some assumptions, there are actually infinitely many solutions. – danbanica Apr 19 '17 at 14:50
0

Well its unrealistic to me that both algorithms took 10 sec for n=10000. Having said that. Here is how I would try to computer this.

K*(n1)^3 = 10sec K*(n2)^3 = x Where K is machines dependent constant independent of data size. x = (n2/n1)^3*10sec = 9.99sec

Applying same principle for the O(3^N) its gives 10/3^10 sec. which is very small.

Misgevolution
  • 825
  • 10
  • 22