Description

Jaza Khan UCID 30119100

Assignment 2 – Proofs

Given that is the number of unique nodes in a linked list, prove that the runtime of Floyd’s Tortoise and Hare algorithm is in .

PROOF
We begin by analyzing the runtime of this algorithm using the uniform cost criterion in order to form a function .
Suppose this algorithm is executed with an input size .

Lines 86-87 each require 1 step.
In order to analzye the number of steps used when executing the while loop on lines 90-103, we can use a bound function for the loop. This will allow us to find the upper bound for the number of times that the while loop body is executed before this execution of the loop ends.
The body of the while loop contains 8 executable steps, each of which cost 1 step except for the do-while loop on lines 97-100. This do-while loop contains 2 executable steps, each of cost 1. These will be executed at most the length of the cycle ( period ) times.
After the loop, only line 104 still has to be executed, which costs 1 step.
Thus, the number of steps executed for this algorithm at most is:

We will now prove that the runtime of Floyd’s Tortoise and Hare algorithm is in , by application of the definition.

By definition of , we are required to show that there exists a constant and a constant such that for all .

Let and .
Let be an arbitrarily chosen element in the range of such that . We must prove that the claim holds for this choice of .

Then,
since whenever . Since was arbitrarily chosen from , it follows that
for all such that . Since and
are constants, this establishes the claim that they are existentially quantified, as needed to conclude .
We have now proved a result for all in the range of such that .

Another way of proving that Floyd’s Hare and Tortoise algorithm is in linear time is using a limit test for .
By definition of the theorem, if exists and is a real constant — so that in particular, it is not
equal to — then

Since 12 is a real and non-negative constant, it now follows by the Limit Test for that this , where is the unique number of nodes in a linked list.

PROOF
We begin by analyzing the runtime of this algorithm using the uniform cost criterion in order to form a function .
Suppose this algorithm is executed with an input size .

Lines 29-30 each cost 1 step.
Line 40 costs 1 step.

Lines 43-44 cost 1 step each, as we are simply calling the getHeadNode() function.
The for loop on lines 47-49 contains one executable step in the body of the loop. This will be executed at most lengthDiff times, while the loop test itself will be executed at most lengthDiff+1 times.
Line 51 costs 1 step.
In order to analzye the number of steps used when executing the while loop on lines 53-71, we can use a bound function for the loop. This will allow us to find the upper bound for the number of times that the while loop body is executed before this execution of the loop ends.
The body of this while loop contains 9 executable steps, each of which cost 1 step except for the for loop on lines 59-61. Similarly to the previous for loop, we can examine the worst case for this as well and the number of steps it would require at most.
The body of the while loop would execute listLength0 + listLength1 number of times at most, while the loop test would execute that + 2 more steps.
Thus, the number of steps executed for this algorithm at most is:

We will now prove that the runtime of the removeSharedLinkedListNodes algorithm is in , by application of the definition.

By definition of , we are required to show that there exists a constant and a constant such that for all .

Let and .
Let be an arbitrarily chosen element in the range of such that . We must prove that the claim holds for this choice of . Then,
since whenever . Since was arbitrarily chosen from , it follows that
for all such that . Since and
are constants, this establishes the claim that they are existentially quantified, as needed to conclude .
We have now proved a result for all in the range of such that .