1.Matrices
(i)Operations on matrices
Matrix addition
Let , be two matrices.
We define by the formula
.
Multiplication of a matrix by a number
Let be a matrix and let be a number.
We define as follows
Multiplication of two matrices
Let , be two matrices.
We define by the formula
, where
(ii)Diagonal matrices
A quadratic matrix is called diagonal if for
(iii)Symmetric matrices
A quadratic matrix is called symmetric if .
(iv)Computational complexity of operations of adding matrices and multiplying matrices (directly by the definition)
Adding two n times n matrices requires n2 operations of adding numbers. Multiplying two n times n matrices requires n3 operations of multiplying numbers and
(n-1)n2 operations of adding numbers.
- Searching
(i)Worst case behavior of Binary-Search
Theorem
If the number of elements inside the list to be searched equals n, then the Binary-Search algorithm requires [log2n]+1 operations in its worse case.
Steps of proof:
- Make the following observation by doubling the
decision tree
Number of elementsMax number of operations
32
7 3
15 4
31 5
… …
2k-1 k
- Observe what happens in the remaining cases
Number of elementsMax number of operations
2-3 2
4-7 3
8-15 4
16-31 5
… …
from 2k-1 to 2k-1 k
- Switch into logarithmic notation
(ii)Worst case behavior of any search algorithm based on comparing numbers
Theorem
Any search algorithm based on comparing numbers requires [log2n]+1 operations in its worse case.
Steps of proof:
1. Assume that there is an algorithm A, which performs
searching with fewer than [log2n]+1 operations.
The decision tree of algorithm A has depth d
smaller than [log2n]+1. This means that d log2n.
3. The decision tree of A contains at most
1+2+…+2d-1=2d-1
internal nodes.
4. Let m be the number of internal nodes of the decision
tree of A. Algorithm A needs to perform
operations of comparing target elements with all
elements of the list. Therefore nm.
5. We conclude that
nm2d-1-1=n-1.
This is a contradiction, which shows that our
assumption of point 1 fails. There is no algorithm
based on comparing numbers, which performs
searching with fewer than [log2n]+1 operations