Временная сложность выражения

Question

Я пытаюсь найти временную сложность следующего:

Algorithm C solves X by dividing a problem of size n into 2 subproblems of size n/2, recursively solving each sub problem, and then combining the solutions in O(n^3) time.

Моя попытка:

2 T(n/2) + O(n^3)

Могу ли я написать непосредственно, что временная сложность будет: O (n ^ 3)

Answer 1

используя основную теорему, мы можем решить 2 T(n/2), что привело бы к O (n), а затем в соответствии с вопросом добавьте O (n ^ 3)

, таким образом, O(n) + O(n^3)

Как вы уже упоминали, временная сложность будет: O (n ^ 3) , но обязательно решите `2 T (n / 2) ', так как, если эта часть имеет большую сложность, это повлияет на финал результат.