Time complexity of an iteration algorithm

I have an iteration algorithm, where at each iteration the amount of computation decrease gradually. Here is an illustration of my algorithm:

Input size: n and Total iteration = k

iter 1: time taken -> f1 * n
iter 2: time taken -> f2 * n
iter 3: time taken -> f3 * n
iter k: time taken -> fk * n

where f1 > f2 > f3 >...> fk and 0 <= f1, f2,...,fk <= 1

Question: What is the time complexity of this algorithm? is it Big-O(klog n)


I think the question seems vague. I'll explain it in words:

Input for my algorithm is n and I'll run it over k iterations. but on each iteration the input size reduces by a factor which is unknown. there is no pattern in the reduction.

eg :

iter 1: input size = n (always n)
iter 2: input size = n/2 (can change)
iter 3: input size = n/5 (can change)
iter 4: input size = n/8 (can change)
iter k: input size = n/10 (can change)



More specifically:

If the denominators of your example:

iter 1: input size = n (always n)
iter 2: input size = n/2 (can change)
iter 3: input size = n/5 (can change)
iter 4: input size = n/8 (can change)
iter k: input size = n/10 (can change)

are strictly integers, then it is O(n*log k ).

Here's why. For a sequence Xn to be O(Yn), there must exists some M, a real number, and m, an integer, such that Xn < M*|Yn| for all n > m.

Now consider the sequence K = {1, 1/2, 1/3, ... 1/k}. Also consider the sequence N = {1, 2, 3, 4...}.

Now let's let Yn = N^t * K (that's the outer left product of N and K). This sequence Yn is always greater than your sequence, regardless of the values of the fi's.

So Xn < 1 * |Yn|, where Yn is the harmonic series times n. As amit pointed out, Yn falls into O(n*log k), so Xn does also. Since we couldn't have bounded Xn any closer above, our best limiting approximation for Xn is also O(n*log k).

The given information is not enough, all we can determine is that the complexity is O((f1+ ... + fk)*n)1.

Why? I'll show with an example, of two cases for fi - each giving different complexity:

Case 1: fi = 1/2^i In this case, we get n * 1/2 + n* 1/4 + ... + n*1/2^k < n, and the algorithm is O(n)

Case 2: fi = 1/i In this case, we get a harmonic series: n * 1/2 + n*1/3 + ... + n*1/k = n(1/2+1/3+...+1/k) = O(nlogk)

EDIT: based on your comments and edit, it seems that the worst case for the algorithm to run as described (if I understood you correctly) is:

iter1 -> n ops
iter2 -> n/2 ops
iter3 -> n/3 ops
iterk -> n/k ops

If this is indeed the case, it matches the described case2, the total run time is an harmonic series: n + n/2 + n/3 + .. + n/k = n(1 + 1/2 + 1/3 + ... + 1/k), which is O(nlogk).

(1) Strictly mathematically speaking - big O is an upper asymptotic bound, and since fi <= 1, we can deduce the algorithm is O(nk), but it is NOT a strict bound, as the examples show - different fi values can give different strict bounds.

Need Your Help

Swift 2 - UIPickerView values of two components

swift2 uipickerview uipickerviewdelegate

I have a UIPickerView with two components, when I change component[0] the data of thecomponent[1]` is reloaded.

Inserting commands from another file into a gnuplot script in a bash environment

linux bash gnuplot

In my bash script, I am doing a bunch of operations before starting my gnuplot script. My bash script looks like this: