The proof of time complexity of the algorithm is not reliable

Jiang Yongjiang

Email: accsys@126.com

The polynomial in the algorithm theory is P=  ,

Where a_iis the coefficient, k is the positive integer, and n is the integer variable.We know that any integer n can be expressed  as n =, b_jis decimal number.Thus we have

          P=.

So, the highest order item a_kn^k becomes a_kb_m^k10^mk.

For example，n=10⁰+3×10^m，P=5n+n²，Thus

P = 5(1+3×10^m)+ (1+3×10^m)²

= 5+15×10^m+1+6×10^m+9×10^2m

= 6+21×10^m+9×10^2m.

The highest order n² becomes 9×10^2m.

Because Wikipedia says:

"The time complexity of an algorithm is commonly expressed using big O notation, which excludes coefficients and lower order terms."

Therefore we haveO(n^k) = O(10^mk), where n is variable and m is also.

The time complexity of the algorithm represented by large O is a mistake. The above sentence is the wrong rule.This is the key to the error.

The time complexity of the research algorithm must take all the time of the algorithm into account .

2015-6-16