CODEWITHSUNDEEP
algorithmtime-complexitycomplexity-theory
Novice
Novice

Reputation: 13

How to find the execution time of the below mentioned algorithm?

Suppose the running time of a Module A is a constant M and N is the size of the input data.

1. Set J:=N.
2. Repeat Steps 3 and 4 while J>1.
3.   Module A.
4.   Set J:=J/2.
     [End of Step 2 loop.]
5. Return.

Upvotes: 1

Views: 56

Answers (2)

molamk
molamk

Reputation: 4116

TL;DR

The time complexity of this algorithm is in O(log(n))

Explanation

  • Since Module A runs in a constant time M, we can say that its running time is O(1)
  • Same goes for the instruction Set J:=J/2, it runs in O(1)
  • Let's say that the loop at line 2 runs K times in total. So after the loop has finished iterating K times, we will end up with J = 1.
    • After the 1st iteration of the loop, we have N / 2 iterations left. After the 2nd we have N / 4. The 3rd N / 8, the 4th N / 16, and so on.
    • After K iterations (when the loop is done iterating) we will end up with J = 1 = N / (2^K).
    • So N / (2^K) = 1, which gives us N = 2^K. Therefore the number of iterations is K = log2(N)
  • The instructions at each iteration of the loop take O(1), we end up with a total of O(log(N))

Notes

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476547

Given dividing a number by two can be done in constant time, the time complexity of this algorithm is O(log N). For (very) large numbers, dividing by two however takes some extra time: O(log K) with K the value to divide.

The algorithm stops when J is less than or equal to one. So that means that if J=2, then it will take M+1 steps (the time evaluate the module, and one to divide J by two, let us here assume that dividing by two takes constant time).

Now for J=2*K (with K a variable), it takes again M+1 steps to complete the loop, plus the time it takes with J=K to solve the problem.

So that means that we obtain the following equation:

T(1) = 0
T(N) = T(N/2) + M + 1

We see thus that the amount of work grows linear in the number of iterations, and the number of iterations has an upperbound log2 N: if we have to perform K steps, then the initial N is between 2K-1+1 and 2K.

So that means that the total number of steps is bounded by:

T(N) = (M+1) * log2(N)

M is constant, so that means that M+1 is constant, hence the variable part is log2(N). This is an O(log N).

Strictly speaking however if N can be very large, such that we need an arbitrary amount of memory, then division is not constant. If we use a binary number system, we can shift the bits in O(log K) with K the number to divide by two (and log2 k the number of bits).

In that case a step thus takes:

T(1) = 0
T(N) = T(N/2) + M + log2(N)

With K iterations, the number of steps is bounded by:

 K
---
\
/    log2(I) + M
---
I=1

The sum of log2(i) with i from 1 to k is equal to log2(k!), which has as upperbound O(k log k). Since the number of steps k is bound by O(log N), this thus means that the the total time complexity of the divisions is O(log N × log(log N)). The total time complexity of all calls to the module remain O(M×log N) so O(log N), so the time complexity is O(log N × (1+log(log N))), or simpler O(log N + log N×log(log N)).

It is however possible to slightly change the algorithm such that we do not have to perform these divisions explicitly: we can use some sort of cursor that each time moves one step further until N is "exhausted", in which case the time complexity is again O(log N).

Upvotes: 0

Related Questions