Computional complexity of sorted array

Question

Currently, I am doing a project for my university, where I do implement known data structures (array, linked list, BST, etc.) and I have to measure the times some operations on them require. For example, the first one for me was array. I've measured the time for adding an element in the middle of an array (with moving further values ofc, so n = n + 1. It of course gave me O(n), where n is a number of elements. Now I have to check for adding an element to the beginning of array and appending an element to it (adding to the end). I've got 2 simple algorithms (I cannot use STL or boost::):

Adding to the beginning:

void array::beginning_append(int value)
{   
    int *temp = new int[n + 1];
    memcpy(temp + 1, table, sizeof(int) * n);
    n = n + 1;
    temp[0] = value;
    delete[] table;
    table = new int[n];
    memcpy(table, temp, sizeof(int) * n);
    delete[] temp;
}

Appending to the end:

void array::append(int value)
{
    int *temp = new int[n + 1];
    memcpy(temp, table, sizeof(int) * n);
    temp[n] = value;
    n = n + 1;
    delete[] table;
    table = new int[n];
    memcpy(table, temp, sizeof(int) * n);
    delete[] temp;
}

Those are methods or array class, where table and n are members of this class. Now those do not differ that much, I thought their times will be the same, and they are (I checked with QueryPerformanceCounter for big numbers of elements, like 500000, and it gave me O(n) complexity), but my lecturer said that adding to beginning will have O(n) computational complexity, but adding or removing an element from the end will have complexity of O(1), so it will be const, no matter of the number of elements. So I would like to ask you guys if my algorithms are bad, I mean they do unnecessary stuff, and that's why they rely on number of elements, or my lecturer was just wrong

I prolly should do that :D When I'm coding, my ability to speak, or write proper english decreases, so f.e I write `beggining` instead of `beginning` — minecraftplayer1234, Mar 11 '17 at 11:33
The times don't differ because in both cases you are reallocating and copying the entire array. If you want to understand why appending to the end is constant, read up about _amortized constant time_ — paddy, Mar 11 '17 at 11:33
@paddy, yes I know. But I have to do that, how can I remove an element without shrinking the array? — minecraftplayer1234, Mar 11 '17 at 11:34
Prolly my computers architecture lab guy would kill me if I would leave something unused in memory :D — minecraftplayer1234, Mar 11 '17 at 11:37
Try this one http://stackoverflow.com/questions/13215645/freeing-last-element-of-a-dynamic-array — AchmadJP, Mar 11 '17 at 11:40

score 3 · Accepted Answer · edited May 23 '17 at 12:00

3

Both complexities are:

O(n)

because you are copying the entire array.

See more about complexity of memcpy() here.

Tip: You could easily skip the second copy, by freeing the memory table is pointing to, and then making it point temp. That way you will copy only once, not twice. However, the overall time complexity will not change.

Example:

void array::prepend(int value)
{   
    int *temp = new int[n + 1];
    memcpy(temp + 1, table, sizeof(int) * n);
    n = n + 1;
    temp[0] = value;
    delete[] table;
    table = temp;
}

Pro tip: How do you detect/avoid Memory leaks in your (Unmanaged) code?

_{Hunch: A clever implementation of realloc() should execute faster than a brute memcpy() to a new array. The reason is that if realloc() is able to grow/shrink your array without having to copy the whole thing into a new location (which can occur when there is simple not enough contiguous space), then it will be faster. realloc() does not mean O(1) always.}

edited May 23 '17 at 12:00

Community

1
1

answered Mar 11 '17 at 11:34

gsamaras

71,951
46
188
305

There is this line: `n = n+1` – minecraftplayer1234 Mar 11 '17 at 11:36
Point is: why you copy the array twice? Just make table point temp – Jack Mar 11 '17 at 11:37
Yes, i know, thats right. I didn't use `cpp` for a long time and I was curious if I make table point to temp, then I have to delete[] temp, or not, but now I think I don't :D Am I correct? – minecraftplayer1234 Mar 11 '17 at 11:39
@Frynio memory that has been dynamically allocated *must* be deallocated by you, see my updated answer please. – gsamaras Mar 11 '17 at 11:40
I know, I did `delete[] table` and then `table = temp`, I guess that's ok, right? – minecraftplayer1234 Mar 11 '17 at 11:41
Yeah, but the order matters. First delete then assign the pointer elsewhere, otherwise you will leave the initial memory allocated "forever" @Frynio! – gsamaras Mar 11 '17 at 11:42
So I did this: (after `temp[0] = value`), `delete[] table;`, `table = temp;` and thats it. Im just scared of memory leaks. Is there any? :D – minecraftplayer1234 Mar 11 '17 at 11:51
Yeah @Frynio, just like my example I guess. – gsamaras Mar 11 '17 at 11:53

alain · Answer 2 · 2017-03-11T11:36:02.420

1

Adding to the end can be achieved in O(1) when the buffer is big enough to hold the new element. Usually, when a reallocation is done, the memory size is increased by more than what is needed at the moment, to not have to do reallocations too often.

In this case you would have an average complexity of O(1) and a worst-time complexity of O(n) when a reallocation occurs.

edited Mar 11 '17 at 11:36

answered Mar 11 '17 at 11:34

alain

11,939
2
31
51

I do have to allocate the table dynamically, and the size has to be just as big as the number of elements is – minecraftplayer1234 Mar 11 '17 at 11:35
The stl `vector` for example has a `size` and `capacity` member, `size` is of course always exact. – alain Mar 11 '17 at 11:38
Not to mention [`std::vector::shrink_to_fit`](http://en.cppreference.com/w/cpp/container/vector/shrink_to_fit) – paddy Mar 11 '17 at 11:39
If you can use C style memory management, using realloc() can make you speed up allocation, and let the append be O(1). – Jack Mar 11 '17 at 11:40
@paddy (s)he cannot use STL. – gsamaras Mar 11 '17 at 11:40
I am aware of this. I am simply illustrating that is there for a reason. – paddy Mar 11 '17 at 11:45
@Jack, but can I use `realloc()` if I didn't use `malloc()` before? – minecraftplayer1234 Mar 11 '17 at 11:45
@Frynio afaik no. You can only user new/delete (c++ style) or malloc(/realloc/calloc)/free (c style) – Jack Mar 11 '17 at 11:48
Okay, I checked that. It works (with `realloc()`). And its `O(1)` – minecraftplayer1234 Mar 11 '17 at 11:49
Oops. I guess it doesn't. I mean you prolly were correct, I can't mix `realloc` with `new/delete`. Hmm. @Edit, okay, I was stupid, I only did `realloc()`, wher I should do `table = (int*)realloc()`, now it works – minecraftplayer1234 Mar 11 '17 at 12:14

Computional complexity of sorted array

2 Answers2