# 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)

Update:

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)

## Answers

**EDIT**

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.