Suppose you want to verify if AB = C and A is m by n and B is n by k then, the time taken for this is O(mnk + nk) = O(mnk)
What if you had a vector x, then ABx = Cx... here x is a random vector.
x is of dimensionality k by 1 and created by randomly sampling from a gaussian distribution.
Now the time taken to compute Bx is O(nk) and is of dimentionaity n by 1 and time taken to compute ABx is O(mn). Similarly, time taken to compute Cx is O(mk)...
So the total time taken to verify is O(mn+nk+mk) and not O(mnk)
What if you had a vector x, then ABx = Cx... here x is a random vector.
x is of dimensionality k by 1 and created by randomly sampling from a gaussian distribution.
Now the time taken to compute Bx is O(nk) and is of dimentionaity n by 1 and time taken to compute ABx is O(mn). Similarly, time taken to compute Cx is O(mk)...
So the total time taken to verify is O(mn+nk+mk) and not O(mnk)
No comments:
Post a Comment