An algorithm performs three different operations. The first and second operations are executed O(…
An algorithm performs three different operations. The first and second operations are executed O( nm) and O( n 2) times respectively and the number of executions of the third operation is yet to be determined. These operations have the following impact on an appropriately defined potential function : Each execution of operation J increases by at most n units, each execution of operation 2 increases by 1 unit, and each execution of operation 3 decreases cf> by at least 1 unit. Suppose we know that 1 :5 cf> :5 n 2• Obtain a bound on the number of executions of the third operation.
