Painter puzzle – estimation

by

There are a lot of unknowns here – his walking speed, his painting speed, for how long does the paint in the brush last…

But clearly there are two processes going on here. One is quadratic – it’s the walking to and fro between the paint can and the painting point. The other is linear – it’s the process of painting, itself.

Thinking about the 10th or even the 100th day, it is clear that the linear component becomes negligible, and the process becomes very nearly quadratic – the walking takes almost all the time. During the first few minutes of the first day, on the contrary, it is close to being linear.

We can thus say that the time t as a function of the distance s follows a power law t ~ s^a with a changing coefficient a = 1.0 … 2.0. This also means that s ~ t^b, b = 1/a.

Applying the empirical orders of growth analysis:

The b coefficient between day 1 and day 2 is approximated as

    b(1,2) = log (450/300) / log 2 = 0.585     ;; and so,
    a(1,2) = 1/b(1,2) = 1/0.585 = 1.71

Just as expected, the a coefficient is below 2. Going for the time period between day 2 and day 3, we can set it approximately to the middle value between 1.71 and 2.0,

    a(2,3) = 1.85                    ;; a = 1.0 .... 2.0
    b(2,3) = 0.54                    ;; b = 1.0 .... 0.5
    s(3)   = s(2) * (3/2)^b(2,3)
           = 450 * (3/2)^0.54
           = 560 yards

Thus the distance covered in the third day can be estimated as 560 - 450 = 110 yards.

What if the a coefficient had the maximum possible value, 2.0, already (which is impossible)? Then, 450*(3/2)^0.5 = 551 yards. And for the other extreme, if it were the same 1.71 (which it clearly can’t be, either), 450*(3/2)^0.585 = 570.

This means that the estimate of 110 yards is plausible, with an error of less than 10 yards on either side.

More Related Contents:

  1. Why is the constant always dropped from big O analysis?
  2. What is amortized analysis of algorithms? [closed]
  3. Painter puzzle – algorithmic estimation from first principles
  4. Difference between average case and amortized analysis
  5. How do I search for a number in a 2d array sorted left to right and top to bottom?
  6. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  7. Time complexity of Euclid’s Algorithm
  8. Quick sort Worst case
  9. Is there an efficient algorithm to generate a 2D concave hull?
  10. How to round floats to integers while preserving their sum?
  11. Modulus power of big numbers
  12. Fast algorithm implementation to sort very small list
  13. Compute social distance between two users
  14. Efficient algorithm for ordering different types of objects
  15. How to find two most distant points?
  16. Algorithm to find two repeated numbers in an array, without sorting
  17. How to implement depth first search for graph with a non-recursive approach
  18. Why is the time complexity of both DFS and BFS O( V + E )
  19. How to split a string into words. Ex: “stringintowords” -> “String Into Words”?
  20. reconstructing a tree from its preorder and postorder lists
  21. Find if a point is inside a convex hull for a set of points without computing the hull itself
  22. Why do we ignore co-efficients in Big O notation?
  23. Myers diff algorithm vs Hunt–McIlroy algorithm
  24. Given Prime Number N, Compute the Next Prime?
  25. Randomly choosing from a list with weighted probabilities
  26. Planar Graph Layouts
  27. Compute the area of intersection between a circle and a triangle?
  28. Unbiased random number generator using a biased one
  29. maximum subarray of an array with integers [duplicate]
  30. CUDA stream compaction algorithm

Leave a Comment