Complexity of the memset function in C

c complexity-theory big-o memset
franvergara66 picture franvergara66 · Jul 26, 2012 · Viewed 13.7k times · Source

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?

Answer

R.. GitHub STOP HELPING ICE picture R.. GitHub STOP HELPING ICE · Jul 26, 2012

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.

Related questions

why does accessing an element in an array take constant time?

Lets say I have an array as: int a[]={4,5,7,10,2,3,6} when I access an element, such as a[3], what does actually happen behind the scenes? Why do many algorithm books (such as the Cormen book...) say that it takes a constant …

Read More
How do I determine the size of my array in C?

How do I determine the size of my array in C? That is, the number of elements the array can hold?

Read More
How to initialize all members of an array to the same value?

I have a large array in C (not C++ if that makes a difference). I want to initialize all members of the same value. I could swear I once knew a simple way to do this. I could use memset() …

Read More