CODEWITHSUNDEEP
algorithmtime-complexity
Joe
Joe

Reputation: 11

Based on given time, estimate input size the algorithm can process

If we know the time complexity of an algorithm/program is O(E log V), and have tabled data of its execution times on different input sizes, how would I estimate the input size V this program can accomplish in example 30 seconds? 

+------+---------+
|  V   |    T    |
+------+---------+
|   10 | 0,00018 |
|   20 | 0,00046 |
|   30 | 0,00091 |
|   40 | 0,0018  |
|   50 | 0,0020  |
|   60 | 0,0029  |
|   70 | 0,0038  |
|   80 | 0,0035  |
|   90 | 0,0069  |
|  100 | 0,008   |
|  200 | 0,037   |
|  300 | 0,093   |
|  500 | 0,35    |
|  750 | 0,95    |
| 1000 | 1,87    |
| 1500 | 6,26    |
| 2000 | 13,06   |
+------+---------+

Upvotes: 1

Views: 130

Answers (2)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186803

Time for Linear Approximation; let's do it with a help of R language:

Create a csv file with the last (i.e. the most precise) numbers, say:

V;T
200;0.016
300;0.047
500;0.13
750;0.42
1000;0.82
1500;2.8
2000;5.8

and execute R script

df <- read.csv("C:\\data.csv", header = TRUE, sep = ";")
df$LogV = log(df$V)
df$LogT = log(df$T)

m <- lm(df$logV ~ df$logT)

summary(m)

You'll get

Coefficients:
            Estimate Std. Error t value Pr(>|t|)     
(Intercept) 6.941998   0.020574  337.42 4.34e-12  
df$LogT     0.390779   0.009129   42.81 1.31e-07 
--- Signif. codes:  0 ‘’ 0.001 ‘’ 0.01 ‘’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.04787 on 5 degrees of freedom 
Multiple R-squared:  0.9973,    
Adjusted R-squared:  0.9967  
F-statistic:  1832 on 1 and 5 DF,  
p-value: 1.313e-07

Correlation R is pretty good, and the corresponding formula is

 LogV = 6.941998 + 0.390779 * LogT

Or

 V = Math.Exp(6.941998) * Math.Pow(T, 0.390779)

Note, that we have O(T**0.4) not O(log(T)) in fact; if you test 

  mLog <- lm(df$logV ~ df$T)

you'll have much worse correlation. Let's compare the estimations (Est. V) on existing values T and compare the estimations with actual V:

  V  (Est. V)   T
-----------------
  10 (  25) 0.000
  20 (  36) 0.000
  30 (  48) 0.000
  40 (  66) 0.001
  50 (  66) 0.001
  60 (  77) 0.001
  70 (  86) 0.002
  80 (  82) 0.002
  90 ( 105) 0.003
 100 ( 114) 0.004
 200 ( 206) 0.016
 300 ( 313) 0.047
 500 ( 466) 0.130
 750 ( 737) 0.420
1000 ( 958) 0.820
1500 (1547) 2.800
2000 (2057) 5.800

If we put T = 30 we'll get estimation for V = 3909 or better say V ~ 4000

Upvotes: 2

MBo
MBo

Reputation: 80232

At first you need to know how E depends on V.

If there is no useful info, try to divide the second column values by logarithm of the first column.

Then try to approximate resulting values by some function - seems that quadratic dependence looks reasonable (and number of edges in dence graph is proportional to square of vertex count).

When E=G(V) is found, use result formula to get numerically value of V to reach 30 seconds. For example (with quadratic function):

Time(V) = C*V*V*log(V)

Estimate C constant and find where function Time(V) intersects T=30 seconds horizontal line.

Upvotes: 0

Related Questions