Re: fix git-pack-redundant crashing sometimes

From: Lukas Sandström <lukass@etek.chalmers.se>
Date: Nov 16, 2005, 23:59 UTC
Message-ID: <437BC7D1.1070605@etek.chalmers.se>
In-Reply-To: <437BA6A6.8080900@etek.chalmers.se>

Lukas Sandström wrote:

Show 16 quoted lines

> Linus Torvalds wrote:
> 
>>On Tue, 15 Nov 2005, Alex Riesen wrote:
>>
>>
>>>Sorry, it doesn't. The code loops here:
>>>
>>>401             /* find the permutations which contain all missing objects */
>>>402             perm_all = perm = get_all_permutations(non_unique);
>>
>>
>>Looks like the whole thing is exponential.
>>
> 
> Slightly less, but not far from.
>

After doing some maths; actually it is very exponential. 2**n - 1 to be precise.