Algorithm Complexity: Parameter Nature Changing the Result?
Say, there is such the algorithm:
for (int i = 1; i < k; i++) {
for (int j = 0; j < (n-k)/(k-1); j=j+2) {
someFunction();
}
}
as you can see there is one nested loop and the function. Let the
function's complexity is O(g_i * (log g_i)), where g_i = (n-k)/(k-1) - j.
1) Am I right that if k is a part of n (k = n/b, where b is a constant),
the overall complexity of the algorithm is O(n), even if b is some huge
constant? [someFunction()'s complexity becomes O(1) at each iteration and
multiplying this value to (n-k)/(2*(k-1)) again gives O(1) because of the
k's nature, and the outer loop gives the O(n)]
2) Am I right that if k is a constant (event a huge one), the overall
complexity is O(n^2 * log n'), where n' is [actually don't know, how to
evaluate this] ? [the only inner loop is important in a complexity
evaluation]
No comments:
Post a Comment