CODEWITHSUNDEEP
algorithmmultiplicationstrassen
Diana
Diana

Reputation: 1437

Strassen's multiplication algorithm for n bits numbers (2way split vs 3way split)

There is a version of Strassen's algorithm for integer multiplication that uses a three-way split (division of the n-bit number into 3 parts of n/3 bits) and takes O(n^1.46).

My question is why is this method not generally preferred to the usual one with 2 way split that uses O(n^1.59)? Any ideas or links that can help me understand? (I looked it up online but I couldn't find anything)

Upvotes: 2

Views: 256

Answers (1)

Neithrik
Neithrik

Reputation: 2078

That is because in practise the second one will be slower. O notation doesn't always correspond with real running speed.

Example: 

f(n) = 1000*n
g(n) = n*lg(n)

O(f(n)) is better than O(g(n)), making f(n) "faster", while in practise n will never be large enough for us to prefer f(n).

Upvotes: 2

Related Questions