Search code examples
javascriptmathcomputer-sciencemathematical-optimizationquantization

Big O notation depend on matrix size only or data type(integer, Boolean) as well?


Does the big O notation depend on the dimension of the matrix only? or it will depend on data type(integer or boolean) as well.

Suppose if I have two matrices of size mat=M x N and I have to multiply them. If the data type of matrix is integer the run time on the computer is different but if the data type is bolean[+1,-1] the run time on the computer is reduced. How I can write big O notation by taking into account data type as well.


Solution

  • You don't take it into account; the big-O is the same in all cases. Big-O is about scaling; how much more work do you do as the size of the input grows, relative to the baseline work?

    Unless the algorithm scales to arbitrary bit lengths for each element of the matrix, the difference between boolean and integer would be a constant multiplier, and constant multipliers are ignored in big-O notation. For a choice of 16 vs. 8 vs. 2 vs. 1, it's not really arbitrary growth; 16 bits may take 16 times as long as 1 bit for a 10x10 matrix, but if it also takes 16 times as long as 1 bit for a 20x20, the scaling factor is the same.

    Note: On real hardware, there may be more noticeable changes in performance (matrices that stop fitting in a cache line, or in cache at all can change behavior significantly), but big-O is about idealized computing devices, with no such limitations.