[Algorytmy] Mnożenie rekurencyjne i Optymalny podział

[Idane]

Witam. Zwracam się z prośbą o pomoc w udzieleniu wskazówek w rozwiązaniu dwóch poniższych zadań, gdyż sam za bardzo nie wiem jak się za to zabrać

I. Mnożenie rekurencyjne
Poniższy algorytm wyznacza \(\displaystyle{ yz}\), gdzie \(\displaystyle{ y, z \in \mathbb{N}}\)

Kod: Zaznacz cały

Mnóż(y, z)
1 if z = 0
2 then return 0
3 else if odd(z) 
4 then return Mnóż(2 · y, z div 2) + y
5 else return Mnóż(2 · y, z div 2)

Jaka jest jego złożoność obliczeniowa?

II. Optymalny podział
Załóżmy, że pewien algorytm wykonuje \(\displaystyle{ m^{2}}\) kroków dla \(\displaystyle{ m}\)-elementowej
tablicy (dla \(\displaystyle{ m \ge 1}\)).
Algorytm ten ma być użyty do tablic \(\displaystyle{ A_1}\) i \(\displaystyle{ A_2}\) . Tablice zawierają łączną liczbę \(\displaystyle{ n}\) elementów. \(\displaystyle{ A_1}\) ma
\(\displaystyle{ k}\) elementów, a \(\displaystyle{ A_2}\) ma \(\displaystyle{ n - k}\) elementów (\(\displaystyle{ 0 \le k \le n}\)).
Dla jakiej wartości \(\displaystyle{ k}\) obliczenia będą trwały najkrócej?