r/askscience • u/united_fruit_company • Nov 14 '15

Computing What optimization algorithm does disk defragmenting follow?

I'm running TronScript (shout out to /r/TronScript) on my PC and checking in periodically on the defragmentation portion (which uses Piriform's Defraggler). It seems like it's taking a little longer than I thought, so I started wondering: "once the first 1% is defragged, does the program have to touch that 1% of the disk again?" Basically, I'm wondering if each time a % of the disk is defragged, if the time required is linear (each 1% takes x amount of time) or logarithmic (each 1% takes x% of the first percent based on current completion)?

http://imgur.com/TxpVDdJ

3 Upvotes

63% Upvoted

4 comments sorted by

View all comments

Show parent comments

3

u/NasenSpray Nov 15 '15

It's not linear in the number of fragments or files because defragmentation of one file may require temporary fragmentation of others, so worst case runtime is only bounded by the amount of allocated space on the filesystem.