Время разработки программы?

Question

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

void splitX(int x) {
     if (x<=1) {return x;};
     splitX(n/2);
     System.out.println("splitting in progress");
     splitX(n/2);
     splitX(n/2);
     splitX(n/2);
}

Я довольно новичок в этом, это то, что сделано до сих пор;

T(n) = 4T(n/2)
     = 4^2T(n/2^2)
     = 4^3T(n/2^3)
     = 4^kT(n/2^k)
     = O(log n)

Я на правильном пути, я немного запутался, также вам приходится учитывать линию печати?

Answer 1

Анализ верен до конца, решение - T(n) = O(n^2)

Обратите внимание, что 4^kT(n/2^k) != O(log n), поскольку 4^k не является константой.
Взгляните на анализ:

T(n) = 4T(n/2) = 
     = 4^2T(n/2^2)
     = 4^3T(n/2^3)
     = 4^kT(n/2^k)
     = 4^log(n)*T(1) =
     = 4^log(n) * 1 =
     = (2^log(n))^2 =
     = n^2
     = O(n^2)

Чтобы формально доказать это: мы используем индукцию
основание: T(1) = 1 = 1^2
Предположим, T(n) = n^2 для каждогоk <= n
T(2n) = 4*T(n) =(induction hypothesis) 4*n^2 = (2n)^2

Таким образом, гипотеза об индукции верна и T(n) = n^2

Этот результат также можно проверить на вольфрам альфа

Answer 2

выражение имеет форму

T (n) = 4T (n / 2) + c

теперь примените мастер теорум, используя a = 4, b = 2 и f (n) = c;

T (n) = O (n ^ loga) // основание 2

Т (п) = п ^ 2

Answer 3

Да, в обозначении Big-O это O (log n) нечетно по константе.

Answer 4

Как я вижу, вы делаете log (N) вызовы вашей рекурсивной функции.умножение этого на константу - 4 - не меняет сложности и не приводит к печати линии (для всех потребностей, связанных с домашней работой).