I was discussing with some friends a piece of code, and we discussed about using memset function in C, which is the order in Big-O notation for this function if we initialize an array of size N?
On a system where you have direct access to the page tables and they're stored in a hierarchical way, memset could be implemented in O(log n) by replacing the whole virtual address mapping with copy-on-write references to a single page filled with the given byte value. Note however that if you're going to do any future modifications to the object, the normal O(n) cost of memset would just be deferred to the page fault to instantiate separate copies of the pages when they're modified.