Analisi Algoritmi (con trabocchetti)

[Giova411]

Da libro di testo superfigo propongo, per chi lo volesse, il seguente esercizio:

integer pippo(integer n)
if n<= 2 then return 1
else if n>99 then
   integer i <-- |_ n/2 _|
   return pipp(i) + n*i
else
   return pippo(n-2) + 5

Valutare ordine di grandezza.

[Giova411]

Visto il grande successo ne propongo un altro
Ripeto: io ho già le soluzioni, volevo condividere e/o commentare questo argomento con esempietti.

funzioncina(integer[] A, integer i , integer j)
 if j<i then return 0
 if i = j  then return 1000*A[i]

 integer n <-- j - i + 1
 integer sum <-- 0
 integer k <-- sparan(n) + 1   % sparan(n) è O(1) e "spara a caso" un numero tra 0 e n-1

 for r<--1 to 2^k do   % sì, proprio 2 elevato k
    sum<-- sum + A[i + sparan(n)]

 return sum + funzioncina(A, i, |_ (i+j)/2 _| ) + funzioncina(A, |_ (i+j)/2 _| +1, j)

Trovare un limite superiore