The problem statement: Append the length of the string to the string while the length is less than or equal to 10

Input: "a" -> Output: "a12345678910"

Input: "abcde" -> Output: "abcde5678910"

The solution of the problem would require lesser time for a larger input. What should be the time complexity of this?

  • $\begingroup$ Nothing "has" something named "the big O". You are probably asking for time-complexity of this problem? In which model; TM, RAM, ...? $\endgroup$ – Raphael Jan 22 '17 at 16:12
  • $\begingroup$ Anyway: a) the "question" you quote is not a question but a problem statement; b) I find it unclear, in particular together with the examples. In neither one do I see "the length" of the input appended to it. Please specify more clearly what the computational problem is. Community votes, please: unclear? $\endgroup$ – Raphael Jan 22 '17 at 16:31

Given any reasonable computational model, we can provide an algorithm to solve your problem that reads the input (stopping at $10$ symbols should it be longer), stores the length, and while such length is less than $10$, appends the needed symbols and updates the total length.

This algorithm performs a constant amount of work at most $10$ times, which means that there exists a constant $c$ that bounds the running time for any size of input. By definition, such an algorithm has complexity $\Theta(1)$.

Observe that if you require the output to be a copy of the input for strings longer than $10$, then, depending on your computational model, you might need to physically copy the string, which takes time $\Theta(n)$.

  • $\begingroup$ There is no algorithm in the question. I think it's important for beginners to separate costs of algorithms from complexity of problems as clearly as possible. $\endgroup$ – Raphael Jan 22 '17 at 16:13
  • 1
    $\begingroup$ @Raphael That's certainly true, but "what is the time complexity of the obvious solution under usual assumptions" is a reasonable interpretation of the question, in my opinion. $\endgroup$ – quicksort Jan 22 '17 at 16:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.