CODEWITHSUNDEEP
performancetimecomplexity-theorytime-complexity
xren
xren

Reputation: 1471

Get the running time T(n)

A algorithm core is like the following.

CHECK_VALUE_IN_ARRAY(array, n, value)
for i = 1 to n
    binary_search(array, i, n, value)

And already know binary_search(array,1,n,value)'s T(n) = Theta(lgn) how to get T(n) ?

PS: My steps:

 T(n) = t(n) + t(n-1) + ... + t(1)
      = lg(n) + lg(n-1) + ... + lg(1)
      = lgn!

Is this right?

Upvotes: 1

Views: 62

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

If binary_search(array, i, n, value) searches elements i ... n of the array for value using binary search, then yes, your analysis is correct. The runtime will be

Θ(log 1 + log 2 + log 3 + ... + log n) = Θ(log n!)

Note that by Stirling's approximation, log n! = Θ(n log n), so the total runtime would be Θ(n log n).

Hope this helps!

Upvotes: 1

Related Questions