CODEWITHSUNDEEP
algorithmrecursiontime-complexitybig-orecurrence
George
George

Reputation: 1

Recurrence relation with variable expressed in terms of n

I wrote a recursive algorithm which runs in Θ(n).

One of the recurrence equations for n > 0 is T(n) = T(v) + T(n - 1 - v) + c where c is a constant and v is a variable that can have values in the fixed range n > v > 0.

How do I go about solving or correctly simplifying this equation further?

Upvotes: 0

Views: 200

Answers (2)

templatetypedef
templatetypedef

Reputation: 372784

In the comments you described the behavior of your algorithm as follows: it does a constant amount of work on an empty tree and otherwise does a constant amount of work, then processes the left and right subtrees recursively. Rather than describing the runtime with a recurrence relation like the one you described, you can account for the runtime in a different way: the work done is directly proportional to the number of nodes in the tree, since you can charge each unit of work done to a specific node. As a result, the total runtime is O(n).

Upvotes: 0

user3235832
user3235832

Reputation:

Just repeatedly expand the non-constant term:

enter image description here

The series terminates when:

enter image description here

This means that enter image description here, as the term T(v) will cancel with the denominator in N.

Upvotes: 1

Related Questions