Does a simple for loop have exponential complexity?

Question

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.

Answer 1

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!

Answer 2

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.