Skip to main content
Removed spurious spoiler markup and tag
Source Link
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

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.

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?

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?

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?

added 33 characters in body
Source Link
Tobi Alafin
  • 1.6k
  • 4
  • 17
  • 22

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 functionsalgorithms for accomplishing a task $f(n), g(n)$$f_i(n), g_i(n)$. $f(n) = o\left(g(n)\right)$$f_i(n) = o\left(g_i(n)\right)$
A simple way to compare $f$$f_i$ and $g$$g_i$, is to find their ratio $r(n)$$r_i(n)$
$$r(n) = \frac{g(n)}{f(n))}$$$$r_i(n) = \frac{g_i(n)}{f_i(n))}$$
Express $r(n)$$r_i(n)$ as a polynomial of ,$n$.
$$r(n) = n^{k}, \{k: k \in \Bbb R\}$$$$r_i(n) = n^{k}, \{k: k \in \Bbb R\}$$
$$v = \ceiling{k}$$$$m = \lceil{k}\rceil$$

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

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?

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?

Source Link
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?