Time/space complexity of string splitting/object creation in c++
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]);
}
}
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.