Time/space complexity of string splitting/object creation in c-CodePudding

I'am struggling to figure out the time complexity of a piece of code that I have that takes a user input from 1 line e.g open 1 0, and splits the input via spaces, then allows the user to create a new 'account' object on the heap. I am thinking it is an O(n^2) operation as it contains 2 while loops, plus an additional function call, this could be completely wrong.

int main(){

    std::vector <std::string> parameters;
    std::string userCommand;

    // Make a new account manager object for a new user
    AccountManager accounts = AccountManager();

    while (userCommand != "exit"){

        parameters.clear(); // Clear ready for next command
        std::cout << std::endl << ">>> ";

        std::getline(std::cin, userCommand);
        char* cstr = new char[userCommand.length()   1];
        strcpy(cstr, userCommand.c_str());

        char* token;
        token = strtok(cstr, " ");

        while (token != nullptr){
            parameters.push_back(token);
            token = strtok(nullptr, " ");
        }

        // This calls a function that creates a creates a new object on the heap
        accounts.openAccount(parameters[1], parameters[2]);
    }
}

CodePudding user response：

The complexity is linear in the total user input length on both space and time.

All the individual operations iterate over user input only a constant amount of times, including the inner loop. Therefore with n the total length of user input time the time complexity is Theta(n).

Similarly memory is only used to store a constant multiple of the user input length, implying Theta(n) space complexity.

This is assuming that the AccountManager operations which you didn't elaborate on are not dominating.

CodePudding user response：

Let’s assume n is the number of times the user submitted an input.

Time complexity:

For each n we are iterating over a number of parameters, let's call them m, however in the sample code provided above it seems like you only expect two parameters meaning the iteration here is always constant. If the number of parameters are variant and/or increasing the time complexity would be O(n*m), but if m = 2, O(2*n) becomes O(n) linear time.

Space complexity:

For each user input n we are creating a new account, it's ambiguous how the new account is created or stored from the provided code, but it's clear that for every user input we create a single new account, meaning the space complexity here is also O(n). The space complexity for all other variables are constant and therefore doesn’t affect the overall space complexity.

Note: the openAccount method could be storing accounts using a data-structure, depending on which one, the time-complexity will be affected.