12 ms·
No, it doesn’t. You still need to produce n² zeroes for the result. If you multiply two n × n matrices, the result isn’t a vector; it’s a n × n matrix.
by Someone 4y ago
No, it doesn’t. You still need to produce n² zeroes for the result. If you multiply two n × n matrices, the result isn’t a vector; it’s a n × n matrix.
- rrobukef 4y agoAny reasonable description of the matrix will do. The string "An n by n matrix of all zeroes." can be a good output if correctly defined.
- Someone 4y agoBy that logic, every algorithm is O(1). You first limit it to a single input, then you “correctly define” the output for that input using some fixed length string, and you’re golden.
- rrobukef 4y agoThus the importance of a good definition 'reasonable'. I can't remember the one in that one course 10 years ago. However, yes, there are big differences based on the encoding. Nobody would accept using unary input encoding to artificially inflate the size of the input. It's also why the time-compelixity of prime-testing is sometimes confusing.