Все зависит от того сколько либ подгружает приложение - если много и все уже загружены - то может быть и больше 50% ...
Почитай в хинтах на LFS - там более подробно разжевано ...
А вообще, имеется одна неприятность с elflib - не помню с какой версии она перестала корректно работать с бинарниками застрипаными sstrip (ELFkicker). Кстати, тот же трабл имеется в file > 3.40
помню во времена kde 2.2.x была такая програмулина objprelink, тогда утверждалось что при сборке с участием её все проги из kde должны грузится быстрей, на деле же получалось, что kde начинал глючить не по детски вплоть до падения в корку части приложений при запуске.
Лично пробовал prelink, никакого ускорения при загрузке KDE не было (все требования при установке prelink были выполнены), только некоторые KDEшные программы валится стали.
ТОже что-то не заметил я никакого ускорения при запуске приложений. Даже больше того, после того как прошелся prelink-ом меня не покидает ощущение, что система стала какой-то неустойчивой. Может ни с того ни с сего "задуматься" секунд эдак на 20-30. Иногда KDE "валится", вплоть до сваливания X-ов. Дискеты стали монтироваться с траблами - то смонтировать не может, то отмонтировать, то не записывает, то еще что-то. Вобщем, лучше этим бяком не пользоваться в глобальном масштабе. Может быть только для конкретных программ, на счет которых твердо уверен, что prelink им не повредит.