Covanov and Thomé ( Multiplication): Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
Tags: Manual revert Reverted
No edit summary
Tag: Manual revert
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Time Complexity ==  
== Time Complexity ==  


$O(n \log n {2}^{O(\log*n)})$
$O(n \log n {2}^{({3} \log*n)})$


== Space Complexity ==  
== Space Complexity ==  
Line 27: Line 27:
== Year ==  
== Year ==  


2015
2016


== Reference ==  
== Reference ==  


https://hal.inria.fr/hal-01108166v1/document
https://arxiv.org/abs/1502.02800

Latest revision as of 09:24, 28 April 2023

Time Complexity

$O(n \log n {2}^{({3} \log*n)})$

Space Complexity

$O(n)$ auxiliary?? bits

(^ same as above)

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM?

Year

2016

Reference

https://arxiv.org/abs/1502.02800