14,331,980 members
Rate this:
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"
}```
Posted
Updated 6-Jun-18 1:15am
v2
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:

## 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;...
...

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.

M
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:

## 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:

## 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:

## 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

http://www.assignmenthelp.net/assignment_help/complexity-datastructure-assignment-help.php

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

Top Experts
Last 24hrsThis month
 OriginalGriff 75 Richard MacCutchan 65 RickZeeland 62 TheRealSteveJudge 35 wire_jp 35
 OriginalGriff 2,313 Maciej Los 1,330 phil.o 958 Richard Deeming 590 Richard MacCutchan 401

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