I was given the following assignment by my Algorithms professor:
Write a Python program that implements Euclid’s extended algorithm. Then perform the following experiment: run it on a random selection of inputs of a given size, for sizes bounded by some parameter $N$; compute the average number of steps of the algorithm for each input size $n$ ≤ $N$, and use gnuplot to plot the result. What does $f(n)$—which is the “average number of steps” of Euclid’s extended algorithm on input size $n$ look like? Note that size is not the same as value; inputs of size $n$ are inputs with a binary representation of $n$ bits.
The programming of the algorithm was the easy part but I just want to make sure that I understand where to go from here. I can fix $N$ to be some arbitrary value. I generate a set of random values of $a$ and $b$ to feed into the algorithm. While the algorithm is running, I have a counter that is keeping track of the number of steps (ignoring trivial linear operations) taken for that particular $a$ and $b$.
At the end of this, I sum the lengths of each individual input's $a$ and $b$ binary representation and that is my $x$ value on the graph. My $y$ value would be the counter variable for that particular $a$ and $b$. Is this a correct way to think about it?
As a follow up question, I also know that the best case for this algorithm is $\theta(1)$ and worst case is $O(log(n))$ so my "average" graph should lie between those two. How would I manually calculate this to verify my end result?