CODEWITHSUNDEEP
algorithmperformancebig-o
Leonardo Lopez
Leonardo Lopez

Reputation: 1143

How to analyze the efficiency of this algorithm

FUNCTION SEEK(A,X)
1. FOUND = FALSE
2. K = 1
3. WHILE (NOT FOUND) AND (K < N)
   a.  IF (A[K] = X THEN
       1.  FOUND = TRUE
   b.  ELSE
       1.  K = K + 1
4. RETURN

Analyzing this algorithm (pseudocode), I can count the number of steps it takes to finish, and analyze its efficiency in theta notation, Θ(n), a linear algorithm. OK.

This following code depends on the inner formulas inside the loop in order to finish:

1.  X = 1
2.  B = 1
3.  UNTIL (B > 100)
    a.  B = 2A - 2
    b.  A = A + 3

Clearly it's not as simple as the first one, and I cannot say that the loop repeats 100 times because of the irregular increments of A and B inside the loop. How can I count the number of steps in this specific algorithm in order to study its efficiency?

Upvotes: 0

Views: 148

Answers (1)

andy256
andy256

Reputation: 2881

B depends on A. A is monotonically increased. Hence the loop runs in linear time depending on the initial value of A. A little algebra will tell you what value of A stops the loop.

Upvotes: 2

Related Questions