Datastrukturer och algoritmer (NY)

(Givet att vi använder samma algoritm) Är svaret 6n? Min snabba beräkning på en servett ger svaret $n+6$.

Smutstvätt skrev:

(Givet att vi använder samma algoritm) Är svaret 6n? Min snabba beräkning på en servett ger svaret $n+6$.

Alla bör alltid ha en penna och en servett tillgänglig :-)  Jag får det också till n+6.

Dator A hinner räkna 3×2ⁿ på t sekunder så hinner dator B räkna 3×2⁽ⁿ⁺⁶⁾ på t sekunder.

Annorlunda uttryckt: 3×2ⁿ = 3×2⁽ⁿ⁺⁶⁾/64 = 3×2ⁿ×2⁶/64 = 3×2ⁿ×2⁶/2⁶ (eftersom 2⁶ = 64)

Trevligt att jag inte är helt ute och cyklar, @Lindehaven. :)

För den som vill läsa, detta är min uträkning:

Det tar t sekunder för n inputs. Den nya maskinen är 64 gånger snabbare, och algoritmen bör då ha tidskomplexitet $T_{\mathrm{snabb}}\left(n\right)=\frac{3·2^n}{64}=\frac{3·2^n}{2^6}$. Vi vill nu hitta ett x sådant att $T(x)=t$, med andra ord vill vi hitta ett x sådant att $T_{\mathrm{snabb}}\left(x\right)=T_{\mathrm{långsam}}\left(n\right)$. Vi vill alltså lösa ekvationen $\frac{3·2^x}{2^6}=3·2^n$. 

Vi kan börja med att multiplicera båda led med nämnaren i VL, och sedan förkorta gemensamma faktorer. Då får vi $2^x=2^n·2^6$ (n är något givet värde). Vad blir då x? :)

Och trevligt att någon visar detta från rätt "håll", d v s lösa ekvationen med det okända.