What is the running time of the following algorithm (in terms of -notation)?

Question

Algorithm solves a problem of size as follows: recursively solves 3 subproblems of size - 2, and then constructs the answer for the original problem in time (1).

It seems obvious that the Master theorem cannot be applied here. So, I thought of drawing a recursion tree, but what bothers me is that do I need to consider two cases: when n is odd/even? Or the result sum and hence the running time wouldn't depend on this at all? Thanks in advance.

Hint: can you solve this if the subproblems are of size n-1? How does it change if the subproblems have size n-2? — Henry, Oct 13 '20 at 17:30
@Henry I suppose that on every new level of tree we need to subtract 2 more from n (T(n-2), T(n-4), T(n-6), etc). And the sum limit changes also — Meta, Oct 13 '20 at 18:35

score 2 · Answer 1 · answered Oct 13 '20 at 17:39

2

We'll have to assume that the base case of the recursion occurs when is either 0 or 1. It could also be that the base case occurs when is either 1 or 2, is not allowed to be 0. We don't really know, but it is not that relevant.

In the first case, the number of operations for a given that is odd, is the same as the number of operations for −1. In the second case it would be the same number of operations as for +1.

So, for determining the asymptotic complexity we can look at just the even numbers (or only the odd numbers).

The recursion tree is a perfect 3-ary tree with a height of (+1)/2 or (+2)/2 (again: depending on the base case).

In a perfect 3-ary tree of height h, we have (3^h-1)/2 nodes, so that is O(3^h), which in terms of is O(3^/2) = O((√3)).

answered Oct 13 '20 at 17:39

trincot

317,000
35
244
286

Still don't exactly understand why we can look at just even or odd numbers (not both of them) – Meta Oct 13 '20 at 18:36
Asymptotic means looking at the trend for increasing n. Two consecutive n will have same tree size. Then next increases, then equal again. Etc...... – trincot Oct 13 '20 at 19:09
Did this answer your question? – trincot Oct 18 '20 at 10:47

score 0 · Accepted Answer · answered Oct 13 '20 at 19:20

Another (possibly simpler) solution in addition to the one proposed by @trincot :

T(n)=3T(n-2)+O(1)=...=3^k(T(n-2k)+O(1)).

Let's find out the stopping condition for this recurrence relation, i.e. need to find k for which the following holds: n-2k=0 --> k=n/2 --> T(n)=O(3^n/2)=O(√3ⁿ)

What is the running time of the following algorithm (in terms of -notation)?

2 Answers2