PL - Aula 2
20 de Setembro 2023 - #CP
Note
As resoluções dos exercícios aqui contidos podem conter erros. Se detetares um problema (e se o souberes resolver) por favor contacta-nos.
Note
These resolutions are using the file mmult.c available and developed by the professors.
Ex. 1
a)
What is the complexity of the MM (i.e., in big O notation, where N is the problem size and NxN is the matrix size)?
O()
Big O Notation Cheat Sheet
- Constant: O(1)
- Linear time: O(n)
- Logarithmic time: O(n log n)
- Quadratic time: O(n^2)
- Exponential time: O(2^n)
- Factorial time: O(n!)
What increase in execution time is expected when the N doubles?
Which component of the performance equation is affected (e.g., #I, CPI or Tcc)?