OSDev.org

An O(n) algorithm would be like this An O(1) algorithm would be like this The difference, an O(1) algorithm always executes in the same amount of time no matter what. It is also much faster in must circumstances, as a block of code will execute once only. An O(n) algorithm is a bitmap, for example, you loop through every bit in the map to find a free one. A free list is a O(1) algorithm, it has its info right there. No looping needed.
Graphed, you can see the difference. Here are some links to what these algorithm types look like graphed

Not parameters, but rather finding a place to put the requested allocation. As a simple example, if a free list gets very long, it could take a long search to find a suitably-sized entry, and there's poor cache locality all the way.

Hi,

This is what I like about free stacks as they can be written as O(1).

neon wrote:Hi,

This is what I like about free stacks as they can be written as O(1).

Yep. I am trying to make most of my system use O(1) algorithms, hoping that might be useful if I decide to support hard real time, and is altogether better for performance.