Calculate the running time of an algorithm

Question

The running time satisfies the recurrence T(n) ≤ T(n/2+1)+O(1). Except for the +1 and the ceiling in the recursive argument, which we can ignore, this is the binary search recurrence, whose solution is T(n) = O(log n)

I'm confused about how is T(n) ≤ T(n/2+1)+O(1) calculated to be T(n) = O(log n).

https://stackoverflow.com/a/6094889/12210002 https://stackoverflow.com/q/8185079/12210002 https://cs.stackexchange.com/q/57424/110958 — teddcp, Mar 23 '20 at 06:11
Does this answer your question? [how to calculate binary search complexity](https://stackoverflow.com/questions/8185079/how-to-calculate-binary-search-complexity) — teddcp, Mar 23 '20 at 06:12
@tedd: to be fair, none of the four links you propose actually address _this_ question, which is not about calculating binary search recurrence, but rather why the calculation of a _different_ recurrence comes out the same. May still be a duplicate out there, but I didn't find it, and the ones you're suggesting definitely are not. — Peter Duniho, Mar 23 '20 at 20:04

score 1 · Answer 1 · answered Mar 23 '20 at 05:50

I'm confused about how is T(n) ≤ T(n/2+1)+O(1) calculated to be T(n) = O(log n).

It's not calculated. It's recognized as being the same. That is, the recurrence expressed as T(n) = T(n/2) + O(1) is a "well-known" recurrence corresponding to binary search. And through other analysis it is also "well-known" that the complexity of binary search is O(log n).

Thus, through the transitive property, we can say that since the T(n) in this case is exactly the same as the binary search, then so too is it true that T(n) = O(log n).

See e.g. https://users.cs.duke.edu/~ola/ap/recurrence.html

Recurrence Relations to Remember
My suggestion is to do what we do in our classes: show students the "big five" recurrence
relations below and ask them to remember what algorithms these are associated with. We
ask our students to solve other recurrence relations, but we really want them to reason
about recursive functions using the recurrence relations below more than knowing how to
solve any given recurrence relation. We also want students to be able to derive a
recurrence relation from a recursive function --- more on that later.

    T(n) = T(n/2) + O(1)
    T(n) = T(n-1) + O(1)
    T(n) = 2 T(n/2) + O(1)
    T(n) = T(n-1) + O(n)
    T(n) = 2 T(n/2) + O(n)

Before continuing, or with your class, try to fit each of the above recurrence
relations to an algorithm and thus to its big-Oh solution. We'll show what these
are below. Of course for practice you can ask your students to derive the solutions
to the recurrence relations using the plug-and-chug method.

    Recurrence                          Algorithm               Big-Oh Solution
    T(n) = T(n/2) + O(1)      Binary Search                         O(log n)
    T(n) = T(n-1) + O(1)      Sequential Search                     O(n)
    T(n) = 2 T(n/2) + O(1)    tree traversal                        O(n)
    T(n) = T(n-1) + O(n)      Selection Sort (other n2 sorts)       O(n2)
    T(n) = 2 T(n/2) + O(n)    Mergesort (average case Quicksort)    O(n log n)

Calculate the running time of an algorithm

1 Answers1