Notation
Results 1 to 2 of 2

Thread: Notation

  1. #1
    andras98's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    664
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Notation

    Hi,

    f(n)= 1/(5n^3) + 1 /(36n^4) + 1 / 49n^5


    für 2^n >=10^6

    wie schauts da aus mit...


    f(n) O(.) OMEGA(.) THETA(.)
    -------------------------------------------
    n^3

    1/n^3

    log n


    Besonders die log Spalte würde mich interessieren!

    Danke!!

    Andreas

  2. #2

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    482
    Thanks
    0
    Thanked 0 Times in 0 Posts
    also, n^3 ist sicher drüber, also liegt die Fkt. in O(n^3), da n^3 streng mon. wächst, aber die Fkt. streng mon. fällt.

    1/n^3, damit lässt sie sich von oben beschränken: Jede Funktion liegt immer im Theta ihrer größten Potenz (Beweis im Skriptum), und da hier n^-3 die höchste Potenz der Fkt. ist, liegt sie in Theta(1/n^3) bzw. in Omega(1/n^3) UND O(1/n^3) (also alle 3 ankreuzen!)

    Der Logarithmus wächst ebenfalls str. monoton (wenn auch nicht so schnell wie n^3, aber egal!), d.h. die Fkt. liegt nur in O(log n).

    Vorraussetzung: die Fkt. hat einen ausschließlich positiven Wertebereich, aber das ist bei AlgoDat bis jetzt immer so gewesen!

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •