CODEWITHSUNDEEP
big-otime-complexity
Farsan Rashid
Farsan Rashid

Reputation: 1500

How to perform algorithm running time calculation?

I completely understand Big O notation but while trying to learn karatsuba algorithm the following statement confused me

T(n) = 4T(n/2)+ O(n)
=>T(n) = O(n^2)

How O(n^2) running time is derived from the first statement?

Upvotes: 0

Views: 38

Answers (1)

Matteo Rubini
Matteo Rubini

Reputation: 831

You have T(n) = aT(n / b) + O(n^c) where a=4, b=2, c=1

then https://en.wikipedia.org/wiki/Master_theorem#Case_1

T(n) = O(n^log2(4)) = O(n^2)

Upvotes: 1

Related Questions