From: Lukas Sandström <lukass@etek.chalmers.se>
Date: Wed, 16 Nov 2005 23:59:13 GMT
Subject: Re: fix git-pack-redundant crashing sometimes
Message-ID: <437BC7D1.1070605@etek.chalmers.se>
In-Reply-To: <437BA6A6.8080900@etek.chalmers.se>

Lukas Sandström wrote:
> 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.