my_digital_garden/4a1s/CP/PL - Aula 2.md

dg-publish
true

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)

[!help]- 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()

[!hint]- 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!)

[!help]- What increase in execution time is expected when the N doubles?

[!help]- Which component of the performance equation is affected (e.g., #I, CPI or Tcc)?