Results 1 to 4 of 4

Math Help - Algorithm Analysis - Big-oh, etc...

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    2

    Algorithm Analysis - Big-oh, etc...

    First of all, this is my first post so... Hi. I've already tried using the search function, but couldn't find anything along the lines I was looking for. I'm trying to learn (more) about algorithm analysis - namely big-oh, big-omega and big-theta notation.

    It's probably best that I post an example problem and go from there:

    =======================================

    Show that f(x) = x^2 + 2x + 1 is O(x^2)

    The example proof states:

    Clearly if x > 1 then x^2 > x > 1

    So f(x) = x^2 + 2x + 1

    <= x^2 + 2x^2 + x^2

    = 4x^2

    Using K = 1 and C = 4 as witnesses implies f(x) is O(x^2)

    Alternate witnesses: K = 2, C = 3

    =======================================

    I'm missing more than a few points... How is this (simple) solution derived? In the example, it looks like the elements that aren't x^2 and raised to that and then added up... Is that because x^2 is the biggest term? What are witnesses, where are they used, and why are they given multiple possible values seemingly by magic?

    I'm confused... Does this make sense to anyone?

    Please help! Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Feb 2009
    Posts
    2
    Bump... I still don't get it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2009
    From
    Cairo
    Posts
    5
    Hello Dietrich,




    The Big-Oh is used to express the growth of a function, and when we have two algorithms that we want to compare, it becomes a helpful tool


    Because, assume these two algorithms do complicated operations , and if we write a function to express these operations, it would contain a lot of terms, and may be other complicated functions
    But, if we use Big-Oh, we can replace all these terms by 1 fucntion


    But, in order to do this, this 1 function, should have a rate of growth higher than the other function (the one with too much terms)


    so in the mentioned example, x^2 is the one that has the highest rate, you can draw
    y =x^2, y=2x, y=1
    to verify this


    but actually, it has higher rate after certain x, let's call it k
    y=1 | y= x | y = x^2
    x=0 1 | 0 | 0
    x=1 1 | 1 | 1
    x=2 1 | 2 | 4
    x=3 1 | 3 | 9



    so we notice that x^2 starts to be greater or equal than other terms at x=1 , but at x=0 , the constant function is greater (This example doesn't show it clearly, but in other functions, we could find the function that has high growth rate, have smaller value than other functions, which have smaller growth rate, till some value k, after which the function with high growth rate dominates)


    so to guarantee, that the function we choose, have highest growth rate,
    we declare the function in this form c*(x^2), where c is simply a constant
    and k represents a lower bound for the values of x,
    for ex if k=5 , we can't use c*(x^2) to give estimate for number of operations when x=4, it will give wrong indication


    we call c, k the witnesses


    so what we want to do , is find c and k, so that we can say that this function truly is a good representative.


    So let's say the algorithm, will take value x greater than or equal 1


    f(x) = x^2 + 2x + 1
    f(1) = 1^2 + 2(1) + 1 = 4
    f(2) = 2^2 + 2(2) +1 = 9
    f(3) = 3^2 + 2(3) +1 = 16


    we want the representative function to be greater or equal to the value of f(x), for all values of x>=1




    Here k=1, l
    let's say we will not replace any of the terms, i.e we will keep the representative function
    the same as f(x) , i.e. x^2 + 2x + 1 so the representative function is O(x^2), because x^2 has highest growth rate, so here c=1


    let's try to substitute, (we will start substitution from 1 because we took k as 1)


    -----x^2
    x=1 | 1
    x=2 | 4
    x=3 | 9
    and so on


    we can see that this representative function is very bad, at x=1 it's equal 1, while f(1) = 4, and we said that we want the representative function to be greater or equal to the value of f(x), for all values of x>=1


    so let's replace the 2nd term in f(x) with x^2 also, so the representative function is
    x^2 + 2x^2 +1 = 3x^2 + 1, i.e. O(3x^2), so here c=3


    let's try to substitute, (we will start substitution from 1 because we took k as 1)


    ------3 x^2
    x=1 | 3
    x=2 | 12
    x=3 | 27
    and so on


    we can still see that this function, although it's greater than f(x) at x=2, x=3, but it's still less than f(x) at x=1, and we choose k=1, so we have to search for other function


    ok, let's replace the 3rd term in f(x), and see what happens
    the representative function becomes x^2 + 2x^2 + x^2 = 4x^2, i.e. O(4x^2), so c = 4




    let's try to substitute, (we will start substitution from 1 because we took k as 1)


    ---- 4 x^2
    x=1 | 4
    x=2 | 16
    x=3 | 36
    and so on


    this one is good, it satisfies the condition:
    the representative function to be greater or equal to the value of f(x), for all values of x>=k


    so c=4, k=1


    well, let's say the algorithm takes values greater than or equal 2, i.e. k=2, what value of c, shall we take? Normally, we would do the same previous procedure to get c, but if you notice, in our second trial, we got 3x^2, and at x=2, x=3 , and so on , it will be greater than f(x) for x>=k
    so k=2, c=3


    we can't take the first trial, because it doesn't satisfy the condition at x=2
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2008
    From
    @home
    Posts
    17
    Hi,
    I have a similar question. How can we chose the correct notation
    for the following functions? Please explain.
    {n}^{\sqrt{n}} = ??? (3^n)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithm Analysis
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: July 1st 2009, 05:02 AM
  2. (Another) Algorithm Analysis
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: June 9th 2009, 02:30 AM
  3. Algorithm analysis
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: June 4th 2009, 05:29 AM
  4. Algorithm analysis
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 17th 2009, 08:32 AM
  5. help me to prove this algorithm analysis
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: February 12th 2008, 08:13 PM

Search Tags


/mathhelpforum @mathhelpforum