1. What does it mathematically mean that f(n) = O(g(n)), in your own words? [3]

2. Assuming that f(n) = O(n^2) and g(n) = O(n^2 logn), what should be f(n) + g(n)? Why? Simplify the resulting expression. [3]

3. What is the worst-case time complexity of the function "func2"? Explain. When providing your analysis, don't forget to specify what is the input size. [4]

Is the following function tail-recursive?

def fib (n: int) -> int:
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

What is the main advantage of using tail recursion?

For a function to be recursive (and practical in Python), what should it have?

Is the following function tail-recursive?

def fib (n: int, a: int = 0, b: int = 1) -> int:
    if n == 0:
        return a
    elif n == 1:
        return b
    else:
        return fib(n - 1, b, a + b)

What is the time complexity of the following function if measured with respect to n?

def mystery(n: int) -> None:
    if n <= 0:
        return
    else:
        if n % 2 == 0:
            mystery(n - 1)
        else:
            mystery(n // 2)