def memoized_fibonacci(n):
    """Returns the nth fibonacci number

    Time complexity: O(n)

    Parameters
    ----------
    n : int
        the nth fibonacci position

    Returns
    -------
    int
        the nth fibonacci number
    -------

    >>> memoized_fibonacci(0)
    0

    >>> memoized_fibonacci(1)
    1

    >>> memoized_fibonacci(3)
    2

    """
    cache = {}

    def fib(m):
        if m < 0:
            raise ValueError("Value cannot be negative")
        if m in cache:
            return cache[m]
        if m == 1:
            return 1
        if m == 0:
            return 0
        cache[m] = fib(m - 1) + fib(m - 2)
        return cache[m]

    return fib(n)