How to analyze the efficiency of this algorithm Part 2
Posted
by
Leonardo Lopez
on Stack Overflow
See other posts from Stack Overflow
or by Leonardo Lopez
Published on 2012-10-05T21:35:09Z
Indexed on
2012/10/05
21:37 UTC
Read the original article
Hit count: 411
code-efficiency
|big-theta
I found an error in the way I explained this question before, so here it goes again:
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, T(n), a linear algorithm. OK.
This following code depends on the inner formulas inside the loop in order to finish, the deal is that there is no variable N in the code, therefore the efficiency of this algorithm will always be the same since we're assigning the value of 1 to both A & B variables:
1. A = 1
2. B = 1
3. UNTIL (B > 100)
a. B = 2A - 2
b. A = A + 3
Now I believe this algorithm performs in constant time, always. But how can I use Algebra in order to find out how many steps it takes to finish?
© Stack Overflow or respective owner