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?


closed as unclear what you're asking by David Richerby, Evil, Rick Decker, Juho, cody Jan 31 '17 at 13:33

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.