Skip to main content
1 of 3
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 functions for accomplishing a task $f(n), g(n)$. $f(n) = o\left(g(n)\right)$
A simple way to compare $f$ and $g$, is to find their ratio $r(n)$
$$r(n) = \frac{g(n)}{f(n))}$$
Express $r(n)$ as a polynomial of ,$n$.
$$r(n) = n^{k}, \{k: k \in \Bbb R\}$$
$$v = \ceiling{k}$$

$R(n) = m^{th}$ derivative of $r(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