Question

The coefficients a and b of the line y = ax + b for the least squares fit of the n points (xi , yi) satisfy

i=1 2

Exercise 1: Express the cost to compute a and b as O(f(n)), for some function f. Justify your formula for f(n)

Answer 1

$\sum_{i=1}^{n}x_i$   is the expression to calculate the mean of x.

The mean is calculate by calculating the sum of all terms in the set divided by the number of elements in the set.

So, the time complexities are:

• $T\left ( \sum_{i=1}^{n}x_i \right )=O(n)$
• $T\left ( \sum_{i=1}^{n}x_i y_i \right )=O(n)$
• $T\left ( \sum_{i=1}^{n}x_i^2 \right )=O(n)$
• $T\left ( \left ( \sum_{i=1}^{n}x_i^2 \right )\left ( \sum_{i=1}^{n}x_i^2 \right ) \right )=O(n*n)=O(n^2)$

So,

Time Complexity of a = $T\left ( \sum_{i=1}^{n}x_i y_i \right )+T\left ( \left ( \sum_{i=1}^{n}x_i^2 \right )\left ( \sum_{i=1}^{n}x_i^2 \right ) \right )+T\left ( \sum_{i=1}^{n}x_i^2 \right )+T\left ( \sum_{i=1}^{n}x_i \right )$

$=O(n)+O(n^2)+O(n)+O(n)$

$=O(n^2)$

Time Complexity of b = $T\left ( \sum_{i=1}^{n}y_i \right )+T\left ( \sum_{i=1}^{n}x_i \right )$

$=O(n)+O(n)$

$=O(n)$