Thread: 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.

Bump... I still don't get it.

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

Hi,
I have a similar question. How can we chose the correct notation
for the following functions? Please explain.
$\displaystyle {n}^{\sqrt{n}}$ = ??? $\displaystyle (3^n)$