1
$\begingroup$

I'm wondering if its possible to express the time complexity of an algorithm that relies on convergence using Big $O$ notation.

Is it fair to say that we can't reason about an algorithm's scalability based on input size if we also have to rely on convergence - unless there's some facet of the algorithm's manner of convergence whereby we can mathematically prove that the number of iterations to reach convergence is related to input size (essentially showing that convergence of the algorithm is a function of the input size $N$)?

For instance, I'm using an algorithm called TextRank, which is based on PageRank - except each vertex is a sentence instead of a webpage and each edge represents the similarity between two sentences (or vertices). The algorithm iterates over the vertices in the graph, carrying out a computation to calculate the score of each vertex for an indefinite amount of iterations until the difference between scores from one iteration to the next is below a threshold (we've reached convergence).

I'm thinking that we cannot reason that an input of size N sentences will always converge in the same manner. Two different bodies of text with say $30$ ($N=30$) sentences, could theoretically require a noticeably different number of iterations over the graph to converge.

Is it possible to represent the limiting behaviour of the function in a polynomial expression due to reliance on convergence?

$\endgroup$
1
$\begingroup$

Usually we prove something about the rate of convergence. For instance, we might prove that after $k$ iterations, the relative error is $1/2^k$. Thus if each iteration takes (say) $O(n^2)$ time, and we want an answer that has relative error at most $\epsilon$, then we have found an algorithm whose running time is $O(n^2 \lg (1/\epsilon))$. Notice how the running time now depends both on the input size and on the desired accuracy of the answer.

For instance, PageRank uses power iteration. As you can see from the Wikipedia page on power iteration, it is possible to prove results about its rate of convergence (as a function of the first two largest eigenvalues $\lambda_1,\lambda_2$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.