CODEWITHSUNDEEP
plotbig-oasymptotic-complexity
f1sh3r0
f1sh3r0

Reputation: 55

Determine asymptotic growth rate from plot

im trying to determine the asymptotic growth rate for the plot below, which has a logarithmic x-axis (base 2) and linear y-axis. It seems sub-logarithmic to me, but what how would one exactly determine the rate (in the big-O notation of asymptotic complexity)?original plot original plot above,in the one below the blue line is sqrt(), green log() and the last one the original function

the blue line is now sqrt(), green log() and the last one the original function

Upvotes: 1

Views: 367

Answers (1)

Alexandre Dupriez
Alexandre Dupriez

Reputation: 3036

Under the assumption you can exhibit a constant number c such that f(2^(i+1))/f(2^i)) = c for every integer i, you can consider the fact that

f(2^i) = c.f(2^(i-1)) = c^i.f(1)

So for any integer k,

f(k) = f(2^log2(k))
     = c^log2(k).f(1)
     = k^log2(c).f(1)

I tried to estimate few values of the ratio f(2^(i+1)) / f(2^i):

f(2^12) / f(2^11) ~= 0.250 / 0.175 ~= 1.43
f(2^11) / f(2^10) ~= 0.175 / 0.125 ~= 1.4
f(2^10) / f(2^9)  ~= 0.125 / 0.085 ~= 1.47
f(2^9)  / f(2^8)  ~= 0.085 / 0.070 ~= 1.21

And it becomes too hard to read the values of the function for lower values of x.

It is not clear to me whether you truly have a constant ratio f(2^(i+1))/f(2^i) (you probably need more data for x > 2^13), but, as an example, if you chose to adopt the value of c = 1.4, you'd end up with the function f(k)/f(1) ~= k^0.49 ~= sqrt(k), i.e. 1/f(1).f would be "close" to the square root function.

Disclaimer: Please take "close" here with extra care, as asymptotically, x^(0.5 +/- epsilon) for epsilon > 0 is nothing but far remote from sqrt(x) (I mean - the difference between both functions can be made arbitrarily large as x -> +Inf).

Upvotes: 2

Related Questions