Vinnaren i pepparkakshustävlingen!
2014-11-07, 18:31
  #1
Medlem
Vet inte riktigt vart jag ska börja med denna.

Let f(n) and g(n) be positive integer functions. Prove using the definitions that if g(n) =
O(f(n)), then f(n) + g(n) = Θ(f(n)).

Det jag får från början är ju att f(n) är en övre gräns för g(n), men hur bevisar jag att det finns konstanter så att c1*f(n) =< f(n) + g(n) =< c2*f(n) ?
__________________
Senast redigerad av JustMeBM 2014-11-07 kl. 18:40. Anledning: Bättre rubrik
Citera
2014-11-07, 21:49
  #2
Medlem
g(n) = O(f(n)) betyder att för tillräckligt stora n gäller g(n) ≤ B f(n), där B är någon positiv konstant.

Detta medför att f(n) + g(n) ≤ f(n) + B f(n) = (B+1) f(n).

Eftersom g är positiv gäller dessutom f(n) ≤ f(n) + g(n).

Sålunda gäller f(n) ≤ f(n) + g(n) ≤ (B+1) f(n).

Detta visar att f(n) + g(n) = Θ(f(n)).
Citera

Stöd Flashback

Flashback finansieras genom donationer från våra medlemmar och besökare. Det är med hjälp av dig vi kan fortsätta erbjuda en fri samhällsdebatt. Tack för ditt stöd!

Stöd Flashback