Geek Answers Handbook

Time complexity of an iterative algorithm

I have an iterative algorithm where, at each iteration, the number of calculations gradually decreases. 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? this is Big-O(klog n)

Update:

I think this question seems vague. I will explain it with the words:

The input for my algorithm is n , and I will run it over iterations of k . but at each iteration, the input size decreases by a factor equal to unknown . there is no picture 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)
+4
source share
2 answers

EDIT

More specific:

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 this is O (n * log k) .

That's why. For the sequence Xn O (Yn) , there must exist 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 Yn = N ^ t * K (which is the outer left product of N and K). This Yn sequence is always larger than your sequence, regardless of fi values.

Thus, Xn <1 * | Yn |, where Yn is a harmonic series of times n. As can be seen from the figure, Yn falls into O (n * log k) , therefore, Xn also. Since we could not have bounded Xn, which is closer above, our best limit approximation for Xn is also O (n * log k) .

+2
source

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

Why? I will give an example of two cases for fi - each of which has a 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 the 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 editing, it seems like the worst case is to run the algorithm as described (if I understood correctly):

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

If this is true, it corresponds to the case2 described, the total runtime of the 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, large O is the upper asymptotic estimate, and since fi <= 1 , we can derive the O(nk) algorithm, but this is NOT a strict boundary , as the examples show that different fi values ​​can give different strict restrictions .

+3
source

More articles:


All Articles