How could I reliably do some performance tests in OCaml

I have implemented a tree-based heap of the following type.

type 'a node = {left: 'a tree; right: 'a tree; value: 'a; rheight: int}
and 'a tree = Node of 'a node | Null

It is an abstract type, which implementation resides in a module. I do my testing in a separate file. Besides, I created some functions operating on it (add an element, get the smallest, join two trees, etc.)

Now I'd like to do some performance tests. Suppose all my functions should operate in O(log n)

Iterating the add_element procedure is not a good option. If I add n elements one by one, then it will take O(n log n), so I won't be able to measure the performance of the other functions (which are O(log n)).

Do you have an idea how I could test, whether my functions are really O(log n)