Can anyone tell me what is the time complexity of memset to initialise an array of size N.
Complexity of memset is O(n).
This function has to reset each element and there are n elements – how can it be faster than O(n)?
Every optimization is a tradeoff. It is lazy clearing and while normal array usage is O(n+m) where m is number accesses to array, here it is O(2m) and it depends on relation between the two - if n >> m lazy is better, for n ~= m it is the same and for n << m the first is better…
@betlista >> Agreed. I thought better share it, because neither the intention of the question is clear nor the domain where he is going to apply.