6

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.

Improve this question
15
  • 1
    If your input string is just the bits that represent n, then yes, that statement would be correct. But normally, your loop does something useful, like process some data of length n. Commented Jun 14, 2014 at 16:46
  • 2
    Can you post some pseudocode rather than just an explanation? Your explanation is a bit difficult to follow. But anyway, if each iteration of the for-loop takes log n (I'm just guessing what you meant...), and the loop runs n times, that's O(n log n), which is not exponential in n. Even if it's O(n²), that's still not exponential. Exponential running time would be O(something ^ (something containing n)), and is actually quite rare [citation needed] without recursion, a stack (or similar). Commented Jun 14, 2014 at 16:47
  • 3
    The word "exponential" by itself is meaningless. You have to tell what it is exponential relative to (or "exponential in" as they say). Your for loop is exponential in the number of bits needed to represent the input, but is linear in the input itself. Commented Jun 14, 2014 at 16:50
  • 2
    @uraf doubling n only makes the input size 1 bigger Commented Jun 14, 2014 at 16:55
  • 2
    @asimes yes, linear in n, not linear in the size of the input, that's the confusion OP is having Commented Jun 14, 2014 at 17:03

3 Answers 3

Reset to default
2

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!

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Hi!I read your answer here: stackoverflow.com/a/19647659/1675971 which solved most of my doubts really. =) So primality testing is "easy" even though it is is exponential in it's input?
@digvijay91 Actually, quite the opposite. :-) Testing primality by trying all possible divisors is entirely infeasible for 1024-bit numbers, so the pseudopolynomial time algorithm is not at all efficient. On the other hand, the AKS primarily test, which is strictly polynomial-time, can be used to test for primality on those large inputs.
Took me so long to understand everything being talked about fully. =) Accepting the answer.
I want to link the answer with the for loop code I have added. So if I understand correctly, the C for loop function I have written, is in EXP if the problem was to "do something ordinary" n times from log n bits. However it would be in P if the problem was to "do something ordinary" n times from an input representing n (even if I can represent it in log n bits given the machine architecture). If this is correct, could you add a more clarified version of this in your answer? Otherwise I can add the above lines as a final edit to the question itself.
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.

Improve this answer

5 Comments

I don't fully understand what you are trying to say. I understand that it is the running time is a function of something. You mean to say that in a given context (explicitly or implicitly), the same program can be classed in EXP or polynomial problems?
@digvijay91: Of course, because it depends what you're considering your input size to be.
No, because the definitions of exptime and polynomial time decision problems specify the parameterization (and that the problem has to be a decision problem, which a loop is not).
@Anonymous Ok, I ended up using EXP and P classes :p. I meant not to. But Oli got the right idea what I was trying to say. Yes what you are saying is correct, but the code sample I gave, does it mean it is exponential to write a simple for loop program? It does not have real world implications like those in case of true EXP problems we know and have to solve. If it doesn't AND we are classing it exponential, then something is amiss.
When you say "we are classing it exponential" you're making the mistake of omitting the parameterization you're using. Use overly precise language until your confusion goes away :)
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.