Trying to compare a recursive and an iterative algorithm

Question

I have two algorithms that solve this problem: Generate all sequences of bits within Hamming distance t. Now I want to compare them theoretically (I do have time measurements, if needed).

The iterative algorithm has a complexity of:

O((n choose t) * n)

where n is the length of the bit-string and t is the desired Hamming distance.

The recursive algorithm, they best we have so far is:

O(2^n)

but how to compare these two Time Complexities, without introducing t inside the second Time Complexity? For that reason, I am trying to do that, can you help?

The recursive algorithm:

// 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);
}

n choose t is n!/(t!.(n-t)!) This has a minimum of 1 (with t==0), and a maximum of n!/(n/2)!² (with t==n/2). — Martin Bonner supports Monica
– Martin Bonner supports Monica, Commented Dec 12, 2016 at 17:03
interesting none of the answering algorithms use next_permutation on another vector of bits. — jaggedSpire
– jaggedSpire, Commented Dec 12, 2016 at 17:08
Finally, observe that the recursive complexity is better than 2^n for small t. If t==0, it will return imediately, and if t=1 the "flipped" branch won't recurse further. In addition, if you check changesLeft > i and return, you can return early if t is close to n. — Martin Bonner supports Monica
– Martin Bonner supports Monica, Commented Dec 12, 2016 at 17:09
No @samgak (sorry for the confusion, really). Fix t, let's say to n/2 and compute the Time Complexity of the function, this would be enough, I guess. — gsamaras
– gsamaras, Commented Dec 12, 2016 at 21:50

David Eisenstat · Accepted Answer · 2016-12-13 00:02:12Z

1

The recursive algorithm is O((n choose t) * n) too, by an analysis that charges to each printed combination the cost of the entire call stack at the time that it is printed. We can do this because every invocation of magic (except the two O(1) leaf calls where i < 0, which we could easily do away with) prints something.

This bound is best possible if you assign printing its true cost. Otherwise, I'm pretty sure that both analyses can be tightened to O(n choose t) excluding printing for t > 0, with details in Knuth 4A.

answered Dec 13, 2016 at 0:02

David Eisenstat

65.7k7 gold badges66 silver badges127 bronze badges

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

Comments

Prune · Accepted Answer · 2016-12-12 23:56:29Z

1

At the most general level of time complexity, we have a "worst case" of t = n/2. Now, fix t and gradually increment n. Let's take a starting point of n=8, t=4

C(8 4) = 8*7*6*5*4*3*2*1 / (4*3*2*1 * 4*3*2*1)
    = 8*7*6*5 / 24
n <= n+1 ... n choose t is now

C(9 4) = ...
    = 9*8*7*6 / 24
    = 9/5 of the previous value.

Now, the progression is a little easier to watch.

C( 8 4) = 8*7*6*5 / 24
C( 9 4) =  9/5 * C( 8 4)
C(10 4) = 10/6 * C( 9 4)
C(11 4) = 11/7 * C(10 4)
...
C( n 4) = n/(n-4) * C(n-1 4)

Now, as lemmas for the student:

Find the base complexity, n! / ( (n-1)! ^ 2)
Find the combinatorial complexity of product (n / (n-c)) for constant c

answered Dec 12, 2016 at 23:56

Prune

78k14 gold badges63 silver badges83 bronze badges

Collectives™ on Stack Overflow

Trying to compare a recursive and an iterative algorithm

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related