I'm new in c programming. I have a doubt about the insert in an array. for example in c and java we cannot insert a new element at the end of an array, it will produce an error (for example we initialize an array with size 5 and inserting a new element at the end). In that case we need to create a new array and copy all element in the previous array to this one and delete the previous array. So the space complexity here is O(1). My question is what is the time complexity here. In one blog I saw that it is O(n), but isn't it O(2n). First we are creating a new array time complexity O(n) then deleting the previous array time complexity O(n) so the total time complexity have to be O(2n) ? Can you guys please help me...
Asked
Active
Viewed 522 times
0
-
3`2n` is equivalent to `n` in `O()` notation (see [here](https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities)) – prog-fh Feb 16 '21 at 08:15
-
If you need to copy the whole array, then also the space complexity is O(n) – klutt Feb 16 '21 at 09:29
-
"Big O" is kind of nonsense here (too) since the bottleneck will not only be the internal copying of data done by realloc, but the heap access itself. Where/how/if the OS actually allocated the memory. Then the copying may or may not utilize data cache, which will make a big difference to the execution time. Cache use in turn depends on how the data is allocated and how realloc is implemented. Focus on understanding what parts of the source that actually take execution time or memory, instead of artificial "Big O" numbers that don't say much about program performance at all. – Lundin Feb 16 '21 at 11:38
2 Answers
0
Creating/deleting (malloc/free) a block of memory is not a O(n) but rather O(1) complexity. Copying/moving the elements from one block of memory to another would be O(n).
If you had to call a constructor/destructor for each element, then you would have indeed O(2n) complexity, but if you just 'move' the elements, then the complexity would be O(n).
But like the user prog-fh already stated in the comment above, O(2n) is O(n).
Note: In C, you can copy a block of memory by memcpy, i only considered the elementwise approach (e.g. calling an element copy function or an elementwise assignment operation).
Erdal Küçük
- 4,810
- 1
- 6
- 11
-
« Creating/deleting (malloc/free) a block of memory is not a O(n) but rather O(1) complexity » Hard to tell indeed, but O(1) is probably not exact [either](https://stackoverflow.com/q/282926/11527076) – prog-fh Feb 16 '21 at 09:25
-
Ok, agreed, but unlike in Java or in C++, C does not iterate over the elements and calls a ctor/dtor for each element. It's 'just' the call to malloc/free. What malloc or free does, well that depends on the implementation of these functions but is it fair to say, that the complexity is < O(n), so in order to calculate the complexity for our algorithm, simply call it O(1)? – Erdal Küçük Feb 16 '21 at 09:32
-
-
-
@klutt What i meant in my Note was, consider a char array, copying byte by byte would be O(n), vs. `memcpy` which would be O(n/sizeof(fastest integral type the system uses)) and/or some other 'magic', which makes it faster/more efficient than O(n). – Erdal Küçük Feb 16 '21 at 09:56
-
-
-
Copying a whole array can be lower than O(n) in the average case, if you take the machine and size of arrays into account, but you cannot do lower than O(n) in the general case. At least not without some really fancy parallelism I don't even know if it's theoretically possible. – klutt Feb 16 '21 at 10:03
0
Yes you are technically correct. Before that we have to understand the notation used for time complexities.
Big-O notation: O(n) is an approximation for upperbound (worst case) only and not the exact value, which means, it can be equal to O(c.n). Here as you said c is 2.
So a rough approximation is O(n). Understand that the notations we use are only approximations.
Useful article on time complexities and notations: here
Vijay
- 144
- 9