Memoized Fibonacci and Time Complexity Analysis

You are required to implement a recursive Fibonacci function using memoization. Given a non-negative integer n, your task is to compute the nth Fibonacci number using a memoized approach. In addition, your program should output the time complexity of the memoized Fibonacci function in the second line as O(n) in LaTeX format (i.e., O(n)).

Note: The Fibonacci sequence is defined as follows:

\( F(0)=0, \quad F(1)=1, \quad F(n)=F(n-1)+F(n-2) \) for \( n \geq 2 \).

Your solution must read input from stdin and write output to stdout. The first line of the input contains a single non-negative integer n. Your program should output two lines: the first line is the nth Fibonacci number computed using memoization, and the second line is the time complexity string (i.e., O(n)).

inputFormat

The input consists of a single non-negative integer n (\(0 \leq n \leq 50\)).

outputFormat

The output should contain two lines:

• The first line contains the nth Fibonacci number computed using memoization.
• The second line contains the time complexity of the memoized Fibonacci algorithm in LaTeX format, i.e., O(n).

## sample

0

0
O(n)

</p>