Для решения подхода 3 (разделяй и властвуй), описанного в этой статье о решении leetcode: https://leetcode.com/articles/longest-common-prefix/
Может кто-нибудь подробно объяснить, как сложность времени T (n) = 2T (n / 2) + O (m) становится O (mn)?
T (n) = 2 * T (n / 2) + O (m) = 2 * (2 * (T (n / 4) + O (m)) + O (m)) = ...
Мы можем найти, например, n = 2 ^ 50, у него будет 2 ^ 50 * T (1) + 2 ^ 50 * O (м). Так что ответ O (m * n)