CODEWITHSUNDEEP
loopsmaxpermutationpseudocodediscrete-mathematics
Lifeni
Lifeni

Reputation: 159

Pseudocode: max of inversions

I have the pseudocode:

enter image description here

If A have n random elements. If $n=64$, how many times can "the while loop" at most be run through by a call to $exists(A,n,x)$?. Is there a formula for that? But value for x and A[mid] have effect on the loops, how can I deal with it if I don't know the values?

Upvotes: 1

Views: 85

Answers (1)

Mureinik
Mureinik

Reputation: 311723

The worst case is when x is not in A, and the while loop needs to continue until lo=hi (instead of returning early when x is found).

In every iteration of the loop, the range checked is decreased by half, so at the worst case, it would run log264 = 6 times.

As an exercise, you can assume x is smaller than any element in A and step through the program to confirm. Then repeat the exercise with the assumption that x is larger than any element of A.

Upvotes: 1

Related Questions