CODEWITHSUNDEEP
algorithmperformancebig-o
Sarah
Sarah

Reputation: 13

Strassen's algorithm efficiency help

Hello I am trying to get the efficiency for Strassen's algorithm but need some help. The recurrence relation for the algorithm is the following:

A(n) = 7A(n/2)+18(n/2)^2, for n>1, A(1) = 0.

I've solved it to the point where I have 

a(n) = 6( 7^(log base(2) n) - 4^(log base(2) n) )

Does this mean the efficiency of the algorithm is O( 7^log(n) ) ?

Upvotes: 1

Views: 879

Answers (2)

Slava
Slava

Reputation: 837

I got

A(n) = O(n^(15/4))

recheck later.

Upvotes: 0

kennytm
kennytm

Reputation: 523584

Yes and no.

As you've found,

a(n) = 6( 7^(log₂ n) - 4^(log₂ n) ),

where the 4^(log2 n) can be discarded, and 6 is just a constant factor, so

Complexity = O(7^(log₂ n))

which is similar to what you get. However, the base 2 here is important because it affects the exponent:

   7^(log₂ n) = n^(log₂ 7) = n^2.80735
// 7^(log  n) = n^(log  7) = n^1.94591
// 7^(log₇ n) = n^(log₇ 7) = n

Upvotes: 2

Related Questions