CODEWITHSUNDEEP
algorithmfor-looptime-complexity
digvijay91
digvijay91

Reputation: 697

Does a simple for loop have exponential complexity?

The time complexity of an algorithm is defined as the amount of time taken by it to run as a function of the length of the input.

If I have a simple for loop function in C, which runs for a given input n then:
the length of n is log n(number of bits required to represent it). Since input is log n and the loop runs n times, the code runs exponentially many times in it's input length ( 2^(log n) = n))
C code:

int forfunction(unsigned int n){
  unsigned int i=0;
  for(;i<n;i++){
    // do something ordinary
  }
  return 0;
}

This for loop being an example.

But we will never hear anyone say, that such a for loop program is exponential in it's input (the bits required to store n). Why is it so? The only difference I see is that this is a program and time complexity is defined for an algorithm. But even if it is, then why does this not have an impact/taken into account when we want to do a rough time complexity of a program?

EDIT: Further clarification: I find it reasonable to claim it is exponential in it's input ( might be wrong =) ). If it so, then if a simple for loop is exponential, then what about other hard problems? Clearly this for loop is not a worry for anyone today. Why is it not? Why does this not have (much) real world implications when compared to other hard problems(EXP,NP-Hard,etc...)? Note: I am using hard the way it used to define NP-Hard problems.

Upvotes: 6

Views: 3534

Answers (3)

Vikram Bhat
Vikram Bhat

Reputation: 6246

Techincally speaking the for loop or for that matter all linear programs are exponential in their inputs but this is not used to explain their runtime because for the simple reason that runtime is defined how it varies with change in input . Here in these problems it is considered the no of input bits is constant for example you might define the algorithm for only integer input so its input has always 32 bits so it is considered constant as even if value of n changes no of bits dont so constant terms cannot be used to define growth of algorithm hence omitted.

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372814

Elaborating on @Anonymous's answer: The question you should be asking is "exponential in what?" Ultimately, whether this is exponential time depends on how n is presented to you.

If n is given to you as an explicit binary integer using O(log n) bits, then this function will run in pseudopolynomial time (technically exponential in the number of input bits, but polynomial in the numeric value of the input). This is why simple primality testing algorithms like trial division (divide n by all numbers from 2 up to √n and see if any of them are factors) technically run in exponential time even though they do run in time O(√n).

On the other hand, if n is given to you implicitly using O(n) bits (perhaps as the number of nodes in a graph given an adjacency matrix, or perhaps as the number of characters in a string given a string), then the runtime is polynomial because the input has at least linear size and linear work is done. This is why algorithms like DFS or BFS, which have runtimes of the form O(m + n), run in polynomial time: the number of bits in the input is Ω(m + n).

Hope this helps!

Upvotes: 2

Paul Hankin
Paul Hankin

Reputation: 58271

The amount of time a function takes is a function parameterised by something. Often it'll be the size of the input, but other times it's an explicit parameter, and it's up to you, when you're describing a function, to make it clear what you mean. Because it's often "obvious" what the parameterisation is from context, it's often omitted which leads to a lot of confusion when the parameterisation is not obvious to everyone.

When you add the word "complexity" then all that means is that instead of describing a function, you're saying it belongs to a particular class of functions. It doesn't obviate the need to say what the function is and what its argument is.

Upvotes: 2

Related Questions