CODEWITHSUNDEEP
algorithmtimetime-complexity
Ergysi RM
Ergysi RM

Reputation: 15

Time complexity of the iterative algorithm?

This is the algorithm: I think its time complexity is O(nlogn) but i am not sure

k=1;
while (k<=n) do      
    j=1;
    while (j<=k) do        
        sum=sum+1;
        j=j+1;
    k=k*2;

Upvotes: 0

Views: 2955

Answers (2)

JuniorCompressor
JuniorCompressor

Reputation: 20025

The inner loop at the first time performs 1 iteration, at the second 2 iterations. The sequence goes like 1, 2, 4, 8, 16, 32, ... as long as it is smaller than or equal to n. The sequence may have Θ(log(n)) elements but its sum is Θ(n). This is because

1 + 2 + 4 + ... + 2^k = 2 * 2^k - 1

and we know n/2 < 2^k <= n. So the inner loop is performed Θ(n) times and each inner loop execution requires constant number of instructions.

The rest of the code is just log(n) assignments to j = 1 and log(n) doubles of k.

So the time complexity of the algorithm is Θ(n).

Upvotes: 5

Thom Wiggers
Thom Wiggers

Reputation: 7052

// code                 | max times executed
k=1;                    | 1
while (k<=n) do         | log n
    j=1;                | log n
    while (j<=k) do     | log n * n
        sum=sum+1;      | log n * n
        j=j+1;          | log n * n
    k=k*2;              | log n

So the O complexity would seem to be n log n.

Upvotes: 0

Related Questions