Time-complexity of looking at item in stringbuider - C#

Question

I have some long text saved in StringBuilder and I want to get some specific item

StringBuilder builder = new StringBuilder();
//fill builder
int i = someNumber();
char ch = builder[i];

what is the time-complexity of the last instruction (char ch = builder[i])? Is it constant

O(1)

or is it linear?

O(i)

score 2 · Answer 1 · answered Jan 25 '18 at 10:41

As per Reference Source the StringBuilder class stores strings in a char Array.

Accessing this array via the property getter this[int index] does a few checks and then returns the array item:

    internal char[] m_ChunkChars;                // The characters in this block
    //...more stuff

    [System.Runtime.CompilerServices.IndexerName("Chars")]
    public char this[int index] {
        // 

        get {
            StringBuilder chunk = this;
            for (; ; )
            {
                int indexInBlock = index - chunk.m_ChunkOffset;
                if (indexInBlock >= 0)
                {
                    if (indexInBlock >= chunk.m_ChunkLength)
                        throw new IndexOutOfRangeException();
                    return chunk.m_ChunkChars[indexInBlock];
                }
                chunk = chunk.m_ChunkPrevious;
                if (chunk == null)
                    throw new IndexOutOfRangeException();
            }
        }
        //... more stuff
    }

Thus the complexity is O(1) or constant access time.

score 1 · Accepted Answer · answered Jan 25 '18 at 10:34

1

It is a constant as you are giving exact location to get the element.So in this case O(1). More details here What is the complexity of this simple piece of code?

answered Jan 25 '18 at 10:34

JyothiJ

315
1
11

score 1 · Answer 3 · answered Jan 25 '18 at 10:35

1

char ch = builder[i] is O(1) .

Because StringBuilder used array index.

answered Jan 25 '18 at 10:35

D-Shih

44,943
6
31
51

score 1 · Answer 4 · answered Jan 25 '18 at 10:41

Looking at the implementation of StringBuilder, it is O(1) because is use char[]

    //
    //
    //  CLASS VARIABLES
    //
    //
    internal char[] m_ChunkChars;                // The characters in this block
    internal StringBuilder m_ChunkPrevious;      // Link to the block logically before this block
    internal int m_ChunkLength;                  // The index in m_ChunkChars that represent the end of the block
    internal int m_ChunkOffset;                  // The logial offset (sum of all characters in previous blocks)
    internal int m_MaxCapacity = 0;

Time-complexity of looking at item in stringbuider - C#

4 Answers4