Click here to Skip to main content
14,331,980 members
Rate this:
Please Sign up or sign in to vote.
See more:
“Analzying the following code and answer the complexity of this algorithm
public String getString()
String s= "";
for(int i =0 ; i < LARGE_NUMBER ; i++) {
s += "a"
Updated 6-Jun-18 1:15am
Sandeep Mewara 17-Jul-12 10:57am
Please use 'Have a Question or Comment' link to respond to an answer. It will notify answerer of your comment such that he can come back and reply.

Use Improve Question link to edit/update your question.
Rate this:
Please Sign up or sign in to vote.

Solution 3

I'd say more than O(N), but less than O(N^2).

Probably because the string will need to be reallocated at some point and be copied.

If the string is a STL string (for example), its will be doubled (I think) when it is too small to add a new letter to it.

so you will have :
"" : string size = 0;
"a" : string size = 1; // double the size and copy the string.
"aa" : string size = 2; // double the size and copy the string.
"aaa_" and "aaaa" : string size = 4; // double the size and copy the string
"aaaaa___", "aaaaaa__", "aaaaaaa_", "aaaaaaaa" : string size = 8;...

think about it.

If you need to optimize this, than reserve a large enough string to reduce the number of time the new string will be re-allocated and copied.
(technicality) In the new C++ , the string copy will be mostly eliminated with the use of the "move" operator; so you will only have to resize the string in advance.

Emilio Garavaglia 20-Jul-12 2:59am
Copy vs Move is not involved here: += doesn't copy, it just makes the size counter increment, and the added character copied (it must be, since it has to go into the string buffer from outside: a character, like any built-in type as any "register-wide type" that is "moved" is in fact "copied": you can "move" only things that are accessed indirectly).

If the size goes over the capacity, an new wider buffer is allocated, the content copyed (move and copy characters is exactly the same) and the old buffer dismissed.

You can "move" a buffer from a string to another, but moving buffers in this context make no sense, since to enlarge it you have to change it (hence you need another one).
Maximilien 20-Jul-12 6:04am
When the vector is resized, there will be a copy, and in the new implementation of C++ the move operator will be used (I'm certain I've seen a video about that made by Stephan T. Lavavej of Microsoft )
Emilio Garavaglia 20-Jul-12 7:03am
Yes, but that "move" will move individual characters from the old (small) buffer to the new (large) one, and hence it will not be different from a copy, since you cannot re-use the old buffer.

The advantage happens if the vector is a vector<unique_ptr<something>>: in that case the ptr-s are "moved" from one buffer to the other, in fact disabling the destruction of the pointed objects from the destroying buffer by the ptr-s destructors.
Rate this:
Please Sign up or sign in to vote.

Solution 4

I think it's smaller than O(N^2), because it contains only 1 for loop.
Eugen Podsypalnikov 17-Jul-12 10:54am
The copying after reallocation can take a loop as well...
My result is N^2 (+1 - for copying of the return value) :)
brian 3 17-Jul-12 11:02am
@Eugen ok so what u are saying is that the s+=a will be equivalent to another for loop
Eugen Podsypalnikov 17-Jul-12 11:13am
Yes, it can be equivalent to another loop :)
Rate this:
Please Sign up or sign in to vote.

Solution 5

deppends on implementation of String.
If string holds the LARGE_NUMBER of memory bytes at the start then complexity is O(N).
If string each time enlarges by one byte of memory with further relocation then it is O(N^2).
When there is not known the size before using it, and you need relocation then you can make it faster by doubling memory size when capacity is not enough. I think it should be something like O(log2(N+1)) with adding O(N) for append operation.
Rate this:
Please Sign up or sign in to vote.

Solution 6

It contains only one loop => O(N)+ time(s += "a")* N,
so that is, total time depends from the implementation of the String class

Volynsky Alex 17-Jul-12 15:59pm

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100