I am unable to find a clear definition of term "size of the instance" when considering some algorithmic problem. I came accross a definition that said, that "Size of the instance corresponds to the size of the input array of numbers (in case the input is numeric) or size of the representation of the input."
Is the size of the instance simply size of the input? Or is it size of all the structures used in the algorithm (in that case, it would be the space complexity, right?).
Lets explain it on a specific problem:
a) I have an array of n numbers and I have to sort them in non-decreasing order.
- So the size of the instance is n (those n numbers I have to sort - using for example BubbleSort). Is the size different for some other sort that uses some additional arrays during the sorting process?
b) Find strong components of a graph with n vertices and m edges.
- Is it simply n+m? Or n+2m (if I represent edges by 2*m array)? Or do I have to consider all structures used in my algorithm (in this case it would be Tarjan, I guess).
Thank you for clarification!