Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: I need help with some algorithms problems

  1. Sep 5, 2011 #1
    I'm having problems solving this assignment. I don't understand how to solve for big-oh, big omega or big theta.

    0.1. In each of the following situations, indicate whether f = O(g), or f = Ω(g), or both (in which case f = Θ(g)).

    f(n)---------------------g(n)
    (a) n - 100------------ n - 200
    (b) n^1/2 --------------n^2/3
    (c) 100n + log n--------n + (log n)2
    (d) n log n-------------10n log 10n
    (e) log 2n-------------- log 3n
    (f) 10 log n------------- log(n2)
    (g) n^1.01-------------- n log^2 n
    (h) n^2/log n-----------n(log n)^2
    (i) n^0.1----------------(log n)^10
    (j) (log n)^log n--------- n/log n
    (k) sq root of n----------(log n)^3
    (l) n^1/2 ---------------5^log2 n
    (m) n2^n-------------------3^n
    (n) 2^n------------------ 2^n+1
    (o) n!----------------------2^n
    (p) (log n)^log n------- 2^(log2 n)^2


    0.2. Show that, if c is a positive real number, then g(n) = 1 + c + c2 + . . . + c^n is:
    (a) Θ(1) if c < 1.
    (b) Θ(n) if c = 1.
    (c) Θ(c^n) if c > 1.



    The dashes in the first problem are only meant to separate the two columns for visibility.
    What I know is this. f = O(g) means f <= g. f = Ω(g) means g = O(f). f = Θ(g) means f = O(g) and f = Ω(g). I'm a little confused right now, I'd appreciate some help.
     
    Last edited: Sep 5, 2011
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted