Can someone explain how to find the time complexities of the follwoing functions
ID: 3883558 • Letter: C
Question
Can someone explain how to find the time complexities of the follwoing functions. C++
Explain how to find the time complexities of the follwoing functions. C++ //} bool isPalindrome_type1(string & aString) //test to see if a string is an exact palindrome { string temp: temp = aString: reverse(temp.begin(), temp.end()): return temp == aString: } bool isPalindrome_type2(string& aString) //converts all char to lowercase then calls func isPalindrome_type1 { string allLow(aString): transform(aString.begin(), aString.end(), allLow.begin(),: : tolower): return isPalindrome_type1(allow): } bool isPalindrome type3(string & aString) //removes all punctuation and space characters then call func isPalindrome_type2 { string punchars = " ,.!?": string temp = removeAll(aString, punchars): return isPalindrome_type2(temp): }Explanation / Answer
For the first function
1. first you are reversing the string which means making the first element the last and vice versa. It will take O(n), as it only requires n iterations.(n is length of string)
2.Then you are comparing two strings, which will also take a max of n iterations if you are just comparing ith element of 1st string to ith of second and so on.
3 so final complexity is O(n)+O(n)=O(2n)=>O(n);
For the second and third function
1. The difference will be that many O(n) terms may get added to final complexity. But it will not affect the order as all will be O(n).(Converting to lowercase, removing punctuation and space characters etc).