Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

sebi

Junior Schreiberling

  • "sebi" is male
  • "sebi" started this thread

Posts: 153

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

1

Tuesday, November 5th 2002, 11:03am

D&A - Aufgabe 1 - b)

Kann mir mal wer n Tipp bei Aufgabe 1b) geben ?

Ich soll zeigen, dass
O( [Summe i=0 bis n] q^i ) = O( q^n) ; q>1

aber das erste ist doch immer grösser als das zweite,
wenn ich z.B. schon q=2 wähle, ist O(2^0 + 2^1 + 2²) grösser (und nicht gleich) O( 2²)

??? thanks for any ideas
venturemedia.de - you don't need eyes to see, you need a vision
  • Send private message

cowhen

Muuuh!

  • "cowhen" is male

Posts: 1,374

Date of registration: Dec 13th 2001

2

Tuesday, November 5th 2002, 11:12am

hallo,

wenn du für

sum(q_i)_{i=0}^n = (q^{n+1} -1)/(q-1) setzt kannt du den term abschätzen als:

kleiner gleich c * (q * q^n)/(q-1)

und dann kannst du ein d wählen zu: d := (c*q)/(q-1)


und dann hast du O(bla-aus aufgabenstellung) kleiner d * c^n

und das war dann soziemlich die "=>" -richtung.

für die "<="-richtung geht das analog.


ich hoffe die antowort kommt vielleicht gerade noch rechtzeitig und bringt dir was.

gruss

cowhen
plenty of time to relax when you are dead
  • Send private message

sebi

Junior Schreiberling

  • "sebi" is male
  • "sebi" started this thread

Posts: 153

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

3

Tuesday, November 5th 2002, 11:29am

cool, danke, da wär ich gar nich drauf gekommen :)
mein ewiger dank verfolge dich auf allen wegen und erheitere dein gemüth in dunklen stunden oder so ähnlich :)
venturemedia.de - you don't need eyes to see, you need a vision
  • Send private message