Web Walk

page_list webwalk( page_list start_page )
{
  page_list foundpages = start_page;
  page_list explored_pages;

  while ( foundpages != empty_list )
  {
    any_page = pick any of foundpages;
    newpage = explore(any_page);
    if (newpage == NULL)
    {
      foundpages -= any_page;
      explored_pages += any_page;
    } else
    {
      foundpages += newpage;
    }
  }
  return explored_pages;
}

• Define the ``operations'':

  (1) Done with any_page, (2) Found a new page.

• Define the potential function:

  $$\Phi(f,e) = n - (f + 2 e).$$

  Let n be the size of the final list.

• Define the amortized costs: $\hat{c}_t = 0$.
• Show that $c_t \le \hat{c}_t + \Phi(x_{t-1}) - \Phi(x_t)$:

  In all cases, c_t = 1.

  (1) Done with any_page:

  

  (2) Found a new page:

  

• Now, the total work in the sequence of operations is bounded by the maximum initial value of the potential function: $\Phi(f_0,e_0) = n -(f_0+2e_0) = n-1$.