On Mon, 5 Aug 2024 17:23:46 GMT, Afshin Zafari <azaf...@openjdk.org> wrote:
>> It is considered that `malloc` or other external events are the same for two
>> cases. If we know that there might be some noise for one or another, we
>> should check and disable them. This is the approach I have talked. How can
>> we avoid noise from `malloc` side?
>
> When it is said that an algorithm has the log(n) time-complexity, it means
> that if the input grows n times, the times grows log(n) times. The tree
> data-structure has log(n) time-complexity. VMATree may have not exactly
> log(n) response times due to self-balancing costs. But it is still expected
> to be less than O(n).
Hi Afshin, could we take a step back and do some asymptotic time complexity
analysis of this problem?
The test is measuring the following code:
```c++
for (int i = 0; i < n; i++) {
int a = (os::random() % n) * 100;
treap.upsert(a, 0);
}
So this algorithm is the tme complexity which we are trying to understand.
First, let's simplify the code slightly:
```c++
auto f = [&](auto n) { int a = (os::random() % n) * 100; treap.upsert(a, i); };
for (int i = 0; i < n; i++) {
f(i);
}
Clearly, `f(n)` is executed `n` times, agreed? Then the time complexity of the
whole program must be `O(n*f(n))`, correct? It's the time complexity of `f(n)`
performed `n` times.
Let's replace `f` with something else to see if we can understand the time
complexity of the whole code snippet again.
```c++
int arr[n];
auto f = [&](auto n) { arr[n] = 0; };
for (int i = 0; i < n; i++) {
f(i);
}
Now, we both agree that assigning to an array has time complexity `O(1)`,
correct? Then, if we fill that in in our expression `O(n * f(n))` we receive
`O(n * 1) = O(n)`, correct? In other words, the time complexity of the
algorithm the test is measuring is *linear*, and we ought to expect that with
an array the time taken for the array should be 10x longer with 10k elements as
compared to 1k elements.
OK, now let's *assume* that `f(n)` has time complexity `O(log n)`, then
shouldn't the algorithm we're measuring have time complexity `O(n * log n)`,
that is actually *slower* than `O(n)`.
In conclusion: if `treap.upsert()` has time complexity `O(log n)` then the
whole algorithm should have time complexity `O(n * log n)` and the measurements
we're seeing are as expected *and the test shouldn't fail*.
Have I missed anything or made any mistakes? Please let me know.
-------------
PR Review Comment: https://git.openjdk.org/jdk/pull/20425#discussion_r1705025716
