Skip to main content
2 of 3
added 33 characters in body
Tobi Alafin
  • 1.6k
  • 4
  • 17
  • 22

Reasoning on Efficiency (2)

Two algorithms to solve a particular problem can have theur efficiency compared using the $O$ and $o$ notation. However, this is very crude method, and tells us no information on how more effective one is than the other.

Is there a yard stick that can be applied to ALL algorithms, with ALL time complexities, that can be used to evaluate the efficiency of two algorithms?

I actually developed a method for this, but it applies only to polynomial algorithms.

MY METHOD.

Suppose we want to compare two algorithms for accomplishing a task $f_i(n), g_i(n)$. $f_i(n) = o\left(g_i(n)\right)$
A simple way to compare $f_i$ and $g_i$, is to find their ratio $r_i(n)$
$$r_i(n) = \frac{g_i(n)}{f_i(n))}$$
Express $r_i(n)$ as a polynomial of ,$n$.
$$r_i(n) = n^{k}, \{k: k \in \Bbb R\}$$
$$m = \lceil{k}\rceil$$

$R_i(n) = m^{th}$ derivative of $r_i(n)$.
It follows that $R(n)$ is a constant.

My method works nicely for polynomial algorithms, but is completely useless for other time complexities. Is there a more effective yardstick? One that applies to all complexities?

Tobi Alafin
  • 1.6k
  • 4
  • 17
  • 22