CODEWITHSUNDEEP
c++time-complexitybig-o
unity123
unity123

Reputation: 49

How to calculate time complexitiy?

I'm really having trouble calculating big O. I get the basics but when it gets to nested for loops and all that, my mind just blanks out. I was asked to write down the complexity of the following algorithm which I have no clue how to do. The input string contains only A,B,C and D

string solution(string &S) {
    int length = S.length();
    int i = 0;
    while(i < length - 1)
    {
        if ( (S[i] == 'A' && S[i+1] == 'B') || (S[i] == 'B' && S[i+1] == 'A'))
        {
            S = S.erase(i,2);
            i = 0;
            length = S.length();
        }
        
        if ( (S[i] == 'C' && S[i+1] == 'D') || (S[i] == 'D' && S[i+1] == 'C'))
        {
            S = S.erase(i,2);
            i = 0;
            length = S.length();
        }
        
        i++;
    }
    
    return S;
}

What would the big O of this algorithm be?

Upvotes: 0

Views: 131

Answers (4)

Den-Jason
Den-Jason

Reputation: 2573

It's easy to get hung up about the precise detail of how efficient an algorithm is. Fundamentally though, all you're concerned about is whether the operation is:

  • Constant time
  • Proportional to the number of elements
  • Proportional to the square of the number of elements

etc...

Look at this for guidance on how to estimate the Big-O for a compound operation: https://hackernoon.com/big-o-for-beginners-622a64760e2

The big-O essentially defines the worst-case complexity of a method, with particular regard to effects that would be observed with very large n. On the face of it you would consider how many times you repeat an operation, but you also need to consider if any embodied methods (e.g. string erase, string length) have complexity that's "constant time", "proportional to the number of elements", "proportional to the number of elements - squared" and so on.

So if your outer loop performs n scans but also invokes methods which also perform n scans on up to every item then you end up with O(n^2).

The main concern is the exponential dimension; you could have a very time-consuming linear-complexity operation, but also a very fast, say, power-of-4 element. In such a case, it's considered to be O(n^4) ( as opposed to O(20000n + n^4) ) because as n tends to infinity, all of the lesser exponent factors become insignificant. See here : https://en.wikipedia.org/wiki/Big_O_notation#Properties

So in your case, you have the following loops:

  • Repetition of the scan (setting i=0) whose frequency is proportional to number of matches (worst case n for argument's sake - even if it's a fraction, when n becomes infinite it remains significant). Although this is not supposedly the outer loop, it does fundamentally govern how many times the other scans are performed.

  • String scan whose frequency is proportional to length (n), PLUS Embodied loop in the string erase - n in the worst case. Note these operations are performed in isolation, together governed by the frequency of the aforementioned repetition. As stated elsewhere, O(n)+O(n) reduces to O(n) because we only care about exponent.

So in this case the complexity is O(n^2)

A separate consideration when assessing the performance of any algorithm regards how cache friendly it is; algorithms using hashmaps, linked lists etc are considered prima-facie to be more efficient, but in some cases a O(n^2) algorithm that operates within a cache line and doesn't invoke page faults nor cache flushes can execute a lot faster than a supposedly more efficient algorithm that has memory scattered all over the place.

Upvotes: 0

Tony Tannous
Tony Tannous

Reputation: 14861

It is O(n^2).

DDDDDDDDDDDDDDDDDDDABABABABABABABABABABABAB

First n/2 characters are D Last n/2 characters are AB

For each AB, (there are 1/4n such) - O(n)

  • You are resetting i (iterating from start)
  • shifting all successive elements to fill the gap created after erase.

Total:

O(n)*(O(n) + O(n)) = O(n^2)

Upvotes: 5

Paul Joseph
Paul Joseph

Reputation: 32

In big O notation, you give the answer for the worst case. Here the worst case will be that the string does not satisfy any if statements. Then time complexity here will be O(n) because there is only one loop.

Upvotes: -1

Michael
Michael

Reputation: 177

I guess this would be O(n) because there is one loop thats going through the string. The longer the string the more time it takes so i would say O(n)

Upvotes: -1

Related Questions