CODEWITHSUNDEEP
time-complexity
sherrellbc
sherrellbc

Reputation: 4878

How is this algorithm O(n)?

Working through the recurrences, you can derive that during each call to this function, the time complexity will be: T(n) = 2T(n/2) + O(1)

And the height of the recurrence tree would be log2(n), where is the total number of calls (i.e. nodes in the tree).

It was said by the instructor that this function has a time complexity of O(n), but I simply cannot see why.

enter image description here

Further, when you substitute O(n) into the time complexity equation there are strange results. For example,

T(n) <= cn

T(n/2) <= (cn)/2

Back into the original equation:

T(n) <= cn + 1

Where this is obviously not true because cn + 1 !< cn

Upvotes: 0

Views: 54

Answers (1)

dureuill
dureuill

Reputation: 2576

Your instructor is correct. This is an application of the Master theorem.

You can't substitute O(n) like you did in the time complexity equation, a correct substitution would be a polynomial form like an + b, since O(n) only shows the highest significant degree (there can be constants of lower degree).

To expand on the answer, you correctly recognize an time complexity equation of the form T(n) = aT(n/b) + f(n), with a = 2, b = 2 and f(n) asympt. equals O(1). With this type of equations, you have three cases that depends on the compared value of log_b(a) (cost of recursion) and of f(n) (cost of solving the basic problem of length n): 1° f(n) is much longer than the recursion itself (log_b(a) < f(n)), for instance a = 2, b = 2 and f(n) asympt. equals O(n^16). Then the recursion is of negligible complexity and the total time complexity can be assimilated to the complexity of f(n):

T(n) = f(n)

2° The recursion is longer than f(n) (log_b(a) > f(n)), which is the case here Then the complexity is O(log_b(a)), in your example O(log_2(2)), ie O(n).

3° The critical case where f(n) == log_b(a), ie there exists k >= 0 such that f(n) = O(n^{log_b(a)} log^k (n)), then the complexity is: 

T(n) = O(n^{log_b(a)} log^k+1 (a)}

This is the ugly case in my opinion.

Upvotes: 1

Related Questions