It doesn't matter because you're using it to compare different languages. O(1) in Java is different from O(1) in C++, or my goose is a duck
And Knuth invented this notation especially *because* of this problem.
To objectively compare algorithms performance despite different constant factors.
* Pointer in C++ takes 8B (raw) or 16B-24B (shared) and in Java 4B (compressed) or 8B (uncompressed).
* A dynamically allocated object in C++ takes usually 8B-24B overhead (memory allocator bookkeeping + eventual vtable ptr), in Java it is always 16B overhead (vtable ptr + lock/GC record).
* C++ is better at object inlining, because you can manually inline objects - a huge win for arrays of small objects like Point2D. In some extreme cases this leads to saving 2/3 of memory that would Java use.
* C++ can waste quite a lot of memory on fragmentation, Java does not.
* Java can waste quite a lot of memory if you allow for GC being too "lazy", C++ does not.
Anyway, summing it all up, the differences are not *that* huge as you may think. I just checked memory usage of my IDE and guess what... more than 2/3 of memory usage is code. Heap is only 170MB, and I have a several MLOC project open.
How does the Scala code intrnally track when a new element is added or an element is removed? Answer this and I could be wrong, because I can only guess at the implementation.
Ah, this is the problem. So you don't understand what that LINQ / Java / Scala code is doing. No, it doesn't track the original collection. It creates a *lazy filtered view* of the collection. Which means, whenever you iterate it, it applies the filter to the original collection. Therefore no data need ever be copied. The operations filter() in Java or withFilter() in Scala run in O(1) time and memory. That's why it can be called "query". Lazy computation is a very important part of CS. I guess C++ STL designers aren't there yet (they were too busy adding threads and atomics which have been in Java for 10 years or so).
So you're comparing the standard libraries now. Excellent.
Nope. realloc / malloc is slow in C++ not because it is poorly implemented, but because it can't be implemented better in this memory management model. Simply Java model is faster for allocating lots of short-lived objects, e.g. like reallocating vectors, when you don't know the target size. C++ model is better for huge, long lived objects, and better for latency. In Java I can use both, where appropriate.
Whatever, in this particular case Java/Scala/C# do not reallocate any vectors. There are no dynamic allocations happening while the query is running.
Though I honestly don't see why unless Java interfaces directly with the ram and uses a more efficient technique of memory allocation.
It does both.
The memory allocation technique in Java can be illustrated by this pseudocode:
void* malloc(int size)
void* ptr = current_ptr;
current_ptr += size;
This is comparable to a speed of a hand-coded slab allocator in C++, ye much faster than generic new (underlying std vectors and strings).