Search code examples
algorithmperformancegraphcomplexity-theory

What exactly is Input size

When I am about to know some algorithms I confused about what exactly is input size.

For example in travelling sales person problem dynamic programming implementation takes O(2n × n2)

And Kruskal's algorithm takes O(E log V). Though both are graph problems why TSP input size is the number of vertices n and in Kruskal's algorithm the input size is in Edges and Vertices.

How to know exactly what can be taken as input size?

Solution

  • You can state an algorithm's complexity in terms of whatever variables you like.

    You should generally choose them to clearly communicate useful information about the running time of the algorithm.