In this document, we present various types of analysis for the line fitting dynamic programming algorithm.
Below we consider various cases of running time analysis. The algorithm implemented is a case of a 2-D dynamic programming problem.
Hence for every combination of points in the segment, the sum of square of errors is calculated in O(n). Hence, the overall complexity of
the algorithm is O( n^2 * n ), which is, O(n^3)
The algorithm takes O(n^3) time to run, where n is the number of points. This is illustrated by the plot shown below.
| num_points | time_taken(s) |
|---|---|
| 100 | 0.002346 |
| 150 | 0.009063 |
| 200 | 0.01767 |
| 250 | 0.03286 |
| 300 | 0.05361 |
| 350 | 0.08288 |
| 400 | 0.1237 |
| 450 | 0.1593 |
| 500 | 0.2139 |
| 550 | 0.2818 |
| 600 | 0.3622 |
| 650 | 0.4774 |
| 700 | 0.5712 |
| 750 | 0.7016 |
| 800 | 0.8569 |
| 850 | 1.029 |
| 900 | 1.21 |
The running time of the algorithm is independent of the value of penalty per segment ( called c), as illustrated by the plot below:
The number of segments inversely depends on the penalty constant c that is chosen. As c becomes large, we get a single line, and for very small c we get a segment for every point.
| penalty | num_segments |
|---|---|
| 0 | 500 |
| 100 | 428 |
| 200 | 399 |
| 300 | 383 |
| 400 | 365 |
| 500 | 346 |
| 600 | 337 |
| 700 | 320 |
| 800 | 308 |
| 900 | 303 |
We have optimized the algorithm to use less memory.
Formally, the algorithm stores the errors for every iteration but that is actually not necessary.
As evident from the plot below, the memory required by the algorithm is linear w.r.t. the number of points.
| num_points | memory_allocated(bytes) |
|---|---|
| 1 | 81675 |
| 51 | 88975 |
| 101 | 96275 |
| 151 | 104087 |
| 201 | 111387 |
| 251 | 118687 |
| 301 | 126499 |
| 351 | 133799 |
| 401 | 141611 |
| 451 | 148911 |
Below we show the visualization of the algorithm for various test-cases.
