How to Analyze an Algorithm

What to analize

1. time

Time

• from a basic level:
  we just suppose that each statement takes one unit of time.

Space

• how many variables

---

Frequency count method

Algorithm Add(A,B,n)
{
	for(i=0;i<n;i++)                    // n+1
	{
		for (j=0;j<n;j++)               // n * (n+1)
		{
			c[i, j]=A[i, j] + B[i, j];  // n * n
		}
	}
}

Time Complexity

(n+1) + n(n+1) + n² = 2n² + 2n + 1
=> O(n^2)

Space Complexity

A = n^2
B = n^2
C = n^2
n = 1
i = 1
j = 1
total = 3n^2 + 3
=> O(n^2)