Problems with Big O Notation

Question

I created two dictionaries, one using doubly linked lists and another using binary search trees, both with some basic functions. I want to estimate the Big O notation for both dictionaries and compare them alongside the native Python dictionary, but I'm facing some issues.

I know that the native dictionary is supposed to be O(1), the list dictionary O(n), and the tree dictionary O(log(n)), but that's not what I'm finding when I generate dictionaries of all three types randomly. What could be the issue? When I try to plot it, it looks like it's kinda alright, but analyzing the times in a list, they are randomly increasing.

The code:

class dict_linear:
 class Node:
    def __init__(self, key, value, prev=None, next=None):
        self.key = key
        self.value = value
        self.prev = prev
        self.next = next

 def __init__(self):
    self.firstNode = None

 def search(self, key):
    curr = self.firstNode
    while curr is not None:
        if curr.key == key:
            return curr
        curr = curr.next
    return None

 def __setitem__(self, key, value):
    curr = self.search(key)
    if curr is not None:
        curr.value = value
    else:
        new_node = self.Node(key, value)
        if self.firstNode is None:
            self.firstNode = new_node
        else:
            new_node.next = self.firstNode
            self.firstNode.prev = new_node
            self.firstNode = new_node

 def __getitem__(self, key):
    curr = self.search(key)
    if curr is None:
        raise KeyError(f"There was an error with the key '{key}'")
    return curr.value

class dict_binary:
 class Node:
    def __init__(self, key, value, left=None, right=None):
        self.key = key
        self.value = value
        self.left = left
        self.right = right

 def __init__(self):
    self.root = None

 def search(self, curr, key):
    if curr is None or curr.key == key:
        return curr
    elif key < curr.key:
        return self.search(curr.left, key)
    else:
        return self.search(curr.right, key)   

 def insert(self, curr, key, value):
    if key == curr.key:
        curr.value = value
    elif key < curr.key:
        if curr.left is None:
            curr.left = self.Node(key, value)
        else:
            self.insert(curr.left, key, value)
    elif key > curr.key:
        if curr.right is None:
            curr.right = self.Node(key, value)
        else:
            self.insert(curr.right, key, value)

 def __setitem__(self, key, value):
    if self.root is None:
        self.root = self.Node(key, value)
    else:
        self.insert(self.root, key, value)

 def __getitem__(self, key):
    curr = self.search(self.root, key)
    if curr is None:
        raise KeyError(f"There was an error with the key '{key}'")
    return curr.value