Python: Как именно вы можете взять строку, разбить ее, перевернуть ее и снова соединить вместе?

Да, это действительно будет O (n). В худшем случае все ваши if прекратят работу, и будет выполнен последний оператор каждого блока if. Итак, каждая итерация выполняет 6 операторов. Тем не менее, ваша временная сложность будет O (6n), который по-прежнему O (n).