Search code examples
algorithmcode-analysisgenetic-algorithmanalysisnp

Algorithmic Analysis - Are there any algorithms having their best case complexity of the order of n^99?

Are there any algorithms having their best case complexity of the order of n^99? Is this NP complete? If not, how do we analyse such algorithms?

Solution

  • One such problem is a k-clique problem.

    Given a graph of size n, is there any clique with k vertices? (k is considered a constant).

    An obvious brute-force algorithm checks all k-subsets of graph vertices and tests them for being a clique. Since there are 𝓞(nk) k-subsets, and each can be checked in 𝓞(k2) time, the total complexity becomes 𝓞(nkk2) or just 𝓞(nk) (because k is a constant).

    The asymptotically best known algorithm for this problem (totally impractical though) runs in 𝓞(n0.792k).

    By varying k, one can deal in any desired complexity.