[utxaa]

if this was the case - even if rewriting the inode was O(n) - you would have noticed. try ls on a large directory, now touch a file on same directory.