Big-Oh Efficiency

[fading gale]

what would be the big -oh efficiency if lets say you add an element to a vector (size of vector is n) as the second to last element ?

[grand ore]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

[safe tangle]

Okay, lets assume you have n elements in your vector (which is a dynamic array). What would be the runtime of just indexing a single element at the n-1 position? Next, think about how your vector is allocated, because it could change your runtime. Maybe you're using push_back to add your element, which in that case is amortized, meaning a block of memory is allocated so that you don't have to reserve system calls over and over just to add multiple elements. If you use push_back, you can just assume a constant runtime, but if you aren't then think about how you're going to resize your vector. Another way may involve allocating all of the data to a new block of memory, which could be O(n) time. The big oh runtime complexity depends entirely on your implementation.

[hallow steppe]

It's amortized O(1), assuming your objects are not insane. You can implement it via a push_back which is O(1) and a swap of the last 2 elements which really shouldn't depend on the length of the vector, so it's also O(1).

[grand ore]

This question thread is being automatically closed. If your question is not answered feel free to bump the post or re-ask. Take a look at !howto ask for tips on improving your question.