Content deleted Content added
Line 6:
How does this compare with the O((log n)^3) figure given on the Wikipedia page? I don't believe the expression Shor gives and the expression on the Wikipedia page are equivalent, unless the definitions of ''n'' in use are different, or if Shor is measuring something else. (More importantly, how was the O((log n)^3) figure arrived at?) -[[User:Yipdw|Yipdw]] 06:02, 14 May 2006 (UTC)
: Big O notation gives an upper bound on running time, so O((log n)^3) is a weaker statment than O((log n)^2 (log log n) (log log log n)). Eg. Shor's statemtent implies the statement that is given in the Wikipedia. O((log n)^3) could have been arrived at by simply observing that O(log n) contains log log n * log log log n.
==speed of various classical factoring algorithms==
| |||