Data structure and algorithms time computation ?

[mohamedeltair]

Assume the following set of instructions:

1. i = 0
2. if i >= n, goto line 6
3. if A[i] = = x, goto line 7
4. i++
5. goto line 2
6. return false
7. return true

Assume that line i take Ci time, where Ci is a constant. The worst case total time of running this block of code can be calculated as: C1 + (n+1)C2 + nC3 + nC4 + nC5 + C6 = (C2 + C3 + C4 + C5)n + (C1 + C2 + C6) = An + B, where A = C2 + C3 + C4 + C5 and B = C1 + C2 + C6 are both constants.

is this right ?

[helios]

Are you sure step 2 is correct? Shouldn't that be a '>' or '>='?

[mohamedeltair]

sorry it is supposed to be >=, check the edited post

[helios]

Your calculation seems to be the correct running time for the case where x is not found in A, but it doesn't seem clear to me that that is the actual worst case.

Let's call the running time you calculated T1. Suppose A[n - 1] == x. Then
T2 = (C2 + C3 + C4 + C5)(n - 1) + (C1 + C2 + C3 + C7)
T2 = (C2 + C3 + C4 + C5)n - (C2 + C3 + C4 + C5) + (C1 + C2 + C3 + C7)
T2 = (C2 + C3 + C4 + C5)n + (C1 - C4 - C5 + C7)

T2 < T1?
(C2 + C3 + C4 + C5)n + (C1 - C4 - C5 + C7) < (C2 + C3 + C4 + C5)n + (C1 + C2 + C6)
C1 - C4 - C5 + C7 < C1 + C2 + C6
C1 + C7 < C2 + C6 + C4 + C5

[mohamedeltair]

in the last line of your reply you removed C1 from the right side only, so i think you mean that T1 is the worst case in case only C7 < C2 + C6 + C4 + C5, but C7 will be very similar to C6 because both are return statements returning true or false, so i think the inequality will always be correct

in case A[n - 1] == x (T2) we will have the following differences between T1 and T2 for lines 1 to 7:

1: both 1 time
2: T1 (n+1 times), T2 (n times)
3: both n times
4 and 5: T1 (n times), T2 (n-1) times
6: T1 (1 time), T2 (0 times)
7: T1 (0 times), T2 (1 time)

(as i've mentioned above i think lines 6 and 7 will take approximately the same time)

[helios]

in the last line of your reply you removed C1 from the right side only

Oops. An error while copying.

C7 will be very similar to C6 because both are return statements returning true or false, so i think the inequality will always be correct

This is a baseless assumption.

[mohamedeltair]

do you mean that a return statement can take time longer than time of 4 other statements one of them is also a return statement ?

[helios]

I mean that all you know about C1, ..., C7 is that the values exist and are constant. C7 < C2 + C6 + C4 + C5 cannot be proven from this definition, and therefore it's a mistake to treat it as true.

[mohamedeltair]

i understand you but i mean can alike statements (like return statements) take entirely different time than each other to execute ?

[helios]

The problem statement doesn't say anything on the matter.