Consider any algorithm function
f(x0,x1,...xn).
If the output for each combination of input arguments was precomputed into a multidimensional array with n dimensions, could the algorithm that simply lookups the solution for a given call to the function in the array be considered a O(1) algorithm? Like
f (x0,x1,..xn) {
return array[x0][x1]...[xn];
}
It would be O(n), not O(1), since you have to lookup n+1 array indices in order to find the result.
n is the number of arguments of the function - in that case it is O(n).
And the question clearly asks for the complexity depending on n.. I don't think so. I think the OP wants to know how much he can reduce the complexity of his algorithm by storing the results of the first execution and then only performing lookups. As I understand it, what's important here is the complexity of the algorithm, but we have no information at all about it. It would be great the OP provides more information as requested...
If the number of dimensions is variable, for example because your algorithm is dimension-agnostic and applications will use a wildly varying number of dimensions, then it's accurate to state the complexity as O(n) where n is the dimensionality (but typically n refers to the length of the input, d or k would be a more customary variable name). For example, the dimensionality can be a variable in algorithms for integrating or optimizing functions in k-dimensional spaces. Monte Carlo integration has a convergence rate of sqrt(k), for example.
However, usually n will be a small constant and only formally be a variable because we're given an algorithm template, so different algorithms following the same general scheme may use different (but constant) values in its place. Then it isn't an interesting variable and it would be more correct and useful to give the complexity as O(1) w.r.t. whatever other variable you're interested in.
A table lookup is algoritmically an O(1) operation because no matter the size the lookup will be performed in constant time.
n here is a poorly selected metric since n is really the number of variables that has to be read and applied to the array. Even though the operation can be reduced to an execution of O(1) the number of lookups are still n (actually n+1 with a 0 based index) which thus becomes O(n). So due to the unfortunate choice of n it doesn't practically mean anything.
n constant time lookups according to the question?
O(1) and O(n) are equally correct/wrong for that reason. Still we try to avoid compiler optimizations, because what happens if n is a million?
since you have mentioned this, If the output for each combination of input arguments was precomputed into a multidimensional array with n dimensions.
it is surely O(1). that is because you have a limited number of combinations before you call the function f() (since before calling the function f() all the combinations have to be calculated and saved in that multidimensional array). so what you just have to do is access the array for a particular combination of input.
Note, the complexity of this would be O(1) since we are considering the access time of an array to be O(1). if one argues that to access that array, it needs to add the indices to the base address (like a[i] = *(a + i) ), then since there will be n number of additions for n dimensions. the accessing time becomes O(n).
Be careful not to confuse yourself. When we say an algorithm has time complexity O(f(n)), then n denotes the size of the input. In your case, however, the input size is always the same, confusingly also named n, but it would be better to call it c because it does not vary. Thus, you have actually defined an algorithm for a finite problem in which it is pointless to talk about time complexity. The computation time is always the same.
If your question is about a family of algorithms, then in fact the time for the lookup will be Theta(n) because you break this down into n lookups, but the time for initializing the lookup table will be *Theta(D^n * g(n))* if D is the number of values that the x_i can take on and g(n) is the complexity of precomputing the value.
Technically speaking, yes, array access takes O(n) time for n dimensions, when n is unbounded.
Practically speaking, n is never unbounded so that n is O(1), and so is the access time.
Note that precomputation of the array takes time and storage exponential in n (at least 2^n elements), so that situations with n really being unbounded do not arise, and asymptotic analysis on the number of dimensions is of little use.
The C standard recommends to support up to 256 dimensions; no computer on earth could store such an array. I don't think I ever exceeded n=10.
When array accesses follow a simple pattern, such as travelling across a single dimension, smart optimizers take this into account, resulting in O(n + k) access time for k accesses instead of O(nk), i.e. O(1) instead of O(n) per access when k>n. (Both in theory and in practice.)
the order should be O(n), however you may reduce it to lograthmic by using binary search.(In the best case scenario you can have a o(1) complexity)
