complexity analysis of this code

Question

1.48/5 (8 votes)

See more:

“Analzying the following code and answer the complexity of this algorithm

C++

public String getString()
String s= "";
for(int i =0 ; i < LARGE_NUMBER ; i++) {
s += "a"
}

Posted 17-Jul-12 4:25am

brian 3

Updated 17-May-20 22:21pm

Sandeep Mewara

v2

Add a Solution

Comments

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.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Maximilien · Answer 1 · 2012-07-17T04:42:00

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.

M

Posted 17-Jul-12 4:42am

Maximilien

Comments

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.

murad_35 · Answer 2 · 2012-07-17T04:47:00

Solution 4

I think it's smaller than O(N^2), because it contains only 1 for loop.

Posted 17-Jul-12 4:47am

murad_35

Comments

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

armagedescu · Answer 3 · 2012-07-17T06:23:00

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.

complexity analysis of this code

3 solutions

Solution 3

Solution 4

Solution 5

Add your solution here

Preview 0

Existing Members

...or Join us