Time complexity of recursive algorithm with two recursive calls

Question

I am trying to analyze the Time Complexity of a recursive algorithm that solves the Generate all sequences of bits within Hamming distance t problem. The algorithm is this:

// str is the bitstring, i the current length, and changesLeft the // desired Hamming distance (see linked question for more) void magic(char* str, int i, int changesLeft) { if (changesLeft == 0) { // assume that this is constant printf("%s\n", str); return; } if (i < 0) return; // flip current bit str[i] = str[i] == '0' ? '1' : '0'; magic(str, i-1, changesLeft-1); // or don't flip it (flip it again to undo) str[i] = str[i] == '0' ? '1' : '0'; magic(str, i-1, changesLeft); }

What is the time complexity of this algorithm?

I fond myself pretty rusty when it comes to this and here is my attempt, which I feel is no where near the truth:

t(0) = 1 t(n) = 2t(n - 1) + c t(n) = t(n - 1) + c = t(n - 2) + c + c = ... = (n - 1) * c + 1 ~= O(n)

where n is the length of the bit string.

Related questions: 1, 2.

Aziz · Accepted Answer · 2016-12-10 16:56:15Z

5

It's exponential:

t(0) = 1 t(n) = 2 t(n - 1) + c t(n) = 2 (2 t(n - 2) + c) + c = 4 t (n - 2) + 3 c = 2 (2 (2 t(n - 3) + c) + c) + c = 8 t (n - 3) + 7 c = ... = 2^i t(n-i) + (2^i - 1) c [at any step i] = ... = 2^n t(0) + (2^n - 1) c = 2^n + (2^n - 1) c ~= O(2^n)

Or, using WolframAlpha: https://www.wolframalpha.com/input/?i=t(0)%3D1,+t(n)%3D2+t(n-1)+%2B+c

The reason it's exponential is that your recursive calls are reducing the problem size by 1, but you're making two recursive calls. Your recursive calls are forming a binary tree.

edited Dec 10, 2016 at 16:56

answered Dec 10, 2016 at 16:52

Aziz

20.9k8 gold badges68 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

gsamaras Over a year ago

Result feels like correct Aziz, but could you please explain the intuition? I mean the way you crafted out this answer. Learn the man to fish, don't just give him the fish! :D

Aziz Over a year ago

This method of solving the recurrence relation is called "telescoping". You basically substitute the function t(n) over and over, until you are able to determine a pattern in the relation (for a given step i). Then you'll be able to determine the final step with t(0), which is the solution.

gsamaras Over a year ago

Thanks Aziz very much, shouldn't we introduce the changesLeft in the equation somehow? I mean in its iterative version, we did, it's called dist there (I am trying to compare them theoretically). I know that for a given changesLeft, (n choose changesLeft) times, we will reach this line of code: printf("%s\n", str);. I posted a relevant question; if you have some time, please take a look! :)

Collectives™ on Stack Overflow

Time complexity of recursive algorithm with two recursive calls

1 Answer 1

3 Comments

Linked

Hot Network Questions