0
$\begingroup$

Context-:

Problems that can be solved by a computer using no more time than slowly growing function of size of input are called tractable. Polynomial functions are slowly growing functions. Functions that grow faster than any polynomial are deemed to grow too fast.

I googled about input size-:

For sorting arrays-: input size is array size.

For combinatorial problems-: Input size is number of objects

For graphs-: it is number of vertices and edges etc.

But I am still unable to understand what does a function of size of input really means?

$\endgroup$
0
$\begingroup$

"Function of the size of the input" when refering to time, means that the time an algorithm needs to run (that is, the algorithm's complexity) depends on the the number of elements of the input you give to the algorithm.

For example, the complexity of

Input: An array of integers of size n, named arr[n]

for (i = 0; i < 4; i++) return arr[3];

is $O(1)$ which is constant and does not depend on the value of $n$. On the other hand, the following algorithm

Input: An array of integers of size n, named arr[n]

for (i = 0; i < n; i++) print arr[i];

will enter the loop $n$ times, so the time the algorithm needs to run depends on the size of the array which is $n$ and its complexity is $O(n)$.

A "slowly growing function" that is mentioned in your excerpt is a function that is not very steep such as a logarithmic, linear or polynomial function. In the following image you can see some common functions that are fast growing and slowly growing with respect to the size of the input

enter image description here

$\endgroup$
0
$\begingroup$

When we talk about things like Big-O notation for time or space complexity, the result is a function. We say that when a function takes in a value, it is a function "of" that value. (In other words, mathematical functions written $f(t)$ are said to be functions of time or functions with respect to time.)

In this case, we are making a function that takes in the "size of input" -- as you said, the array size, the number of vertices, etc. That allows us to create a function to talk about the performance.

If we say that an algorithm is $O(n^2)$ (for example, Bubblesort), we took in the "size of input" $n$ and created the polynomial function $n^2$ to talk about how fast the function performs in relation to the input size $n$. (For those who don't know what $O(n^2)$ means, a quick analogy: if I multiply the number of records by 3, the resulting time it takes will be multiplied by 9, or $3^2$.) Since $n^2$ is a polynomial time, it is considered a slowly growing function in your definitions. (That being said, there are many much better sorting algorithms -- this is not an advertisement for Bubblesort!)

If we say that an algorithm is $O(2^n)$, this is still a function which makes use of the input size $n$... but since $2^n$ is an exponential function, it is considered to grow too fast to be useful according to your definitions above.

$\endgroup$
1
  • $\begingroup$ wow clear. thanks. $\endgroup$
    – silfeg
    Nov 3 '21 at 15:58

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.