Complexity of the memset function in C
big-o, c, complexity-theory, memset
Solution
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.
Problem
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?