1. Yes.  

We want to know f = O( f * log(f) ),  

--> f <= c * f * log (f)

-->  c * log(f) >= 1

--> c >= 1/ log(f)

when n is large enough (n = infinite) , log(f) >= 1

--> 1/ log(f) <= 1

so there exists c = 1 or 2 ... ( c >= 1), that we can hold f <= c * f * log(f) 

so f = O( f * log(f) )

2. Yes

We want to know g = O(f+g)

--> g <= c * (f + g)

-- > c >= g / ( f + g )

Becuse f > 0, 

-- > f + g > g

-- > g / ( f+g ) < 1

There exists c = 1,2 ( c >= 1), that c >= g / ( f + g )

-- > g <= c * ( f + g)

--> g = O( f + g )

Am I understanding this correctly?

The running time (in its fullest detail) of an algorithm is represented by theta notation. The worst-case scenario is represented by big-oh notation such that given a function f, f is O(g) if there exists a constant c > 0 and n_0 > 0 where f <= c * g. The best-case scenario is represented by big-omega notation such that given a function f, f is Omega(g) if there exists a constant c > 0 and n_0 > 0 where f >= g/c.

I also want to know what is this n_0. From what I learned during group work, n_0 is the intersection between the graphs of functions f and g.

I'm going to give it a try to make it easier to follow along (from my understanding of the explanation):

f = O(f * log(f))

*Note: to set up equations with O(n) remember => 

f = O(n) <==> f <= c * n, where c is a constant

Now, usually it is stated that f(n) > 1, so f == 2 would be a good substitution to use in this problem later:

1) f = O(f * log(f)) ==> f <= c * f * log(f) (divide the fs to make one)

2) (f/f) = c * log(f) ==> 1 <= c * log(f) (in the wikia it is usually said f(n) > 1, so substitute f to be 2)

3) 1 <= c * log(2) (log n is the amount of times n has to be divided by 2 because we are using log base 2 to make one, so log 2 == 1)

if you are confused about log base 2, use this calculator http://www.miniwebtool.com/log-base-2-calculator/, google, or this page http://www.purplemath.com/modules/solvelog2.htm

4) 1 <= c * log(2) ==> 1 <= c * 1 (we usually ignore constants so we'll take it out the next step)

5) 1 <= c * 1 ==> 1 <= 1 (which is true because 1 is equal to itself and so satisfies the condition)

6) Since we broke it down and found out it is true for numbers greater than 1 (e.g. 2, as the log base 2 of 1 == 0, see calculator),

f = O(f * log(f)) is true

Did this make more sense?

AnonCS312 wrote:

I'm going to give it a try to make it easier to follow along (from my understanding of the explanation):

f = O(f * log(f))

*Note: to set up equations with O(n) remember => 

f = O(n) <==> f <= c * n, where c is a constant

Now, usually it is stated that f(n) > 1, so f == 2 would be a good substitution to use in this problem later:

1) f = O(f * log(f)) ==> f <= c * f * log(f) (divide the fs to make one)

2) (f/f) = c * log(f) ==> 1 <= c * log(f) (in the wikia it is usually said f(n) > 1, so substitute f to be 2)

3) 1 <= c * log(2) (log n is the amount of times n has to be divided by 2 because we are using log base 2 to make one, so log 2 == 1)

if you are confused about log base 2, use this calculator http://www.miniwebtool.com/log-base-2-calculator/, google, or this page http://www.purplemath.com/modules/solvelog2.htm

4) 1 <= c * log(2) ==> 1 <= c * 1 (we usually ignore constants so we'll take it out the next step)

5) 1 <= c * 1 ==> 1 <= 1 (which is true because 1 is equal to itself and so satisfies the condition)

6) Since we broke it down and found out it is true for numbers greater than 1 (e.g. 2, as the log base 2 of 1 == 0, see calculator),

f = O(f * log(f)) is true

Did this make more sense?

Since you say that it's said that f(n) > 1, then that means that this question is true:

Do the assumptions that all functions are greater than or equal to 1 and that they never decrease make sense for functions that are supposed to represent the runtime of algorithms? Why or why not?

This is because there is always a runtime for every algorithm. There is no such thing as negative runtime. Correct?

Also, my guess is that you chose 2 to replace f due to the log_2(n) fact. It's for simplicity's sake. For instance, if it was log_3(n), you would've selected 3 to replace f.

I posted questions on each of my posts. I'm not too sure if they were all noticed. Perhaps I should bold my questions?

By the way:

I also want to know what is this n_0. From what I learned during group work, n_0 is the intersection between the graphs of functions f and g.

Also:

Just to double check my understanding, does function g derive from f? Or are they both independent functions? I feel that it is the former.

And to reiterate:

The running time (in its fullest detail) of an algorithm is represented by theta notation. The worst-case scenario is represented by big-oh notation such that given a function f, f is O(g) if there exists a constant c > 0 and n_0 > 0 where f <= c * g. The best-case scenario is represented by big-omega notation such that given a function f, f is Omega(g) if there exists a constant c > 0 and n_0 > 0 where f >= g/c.

AnonCS312 wrote:

By the way:

I also want to know what is this n_0. From what I learned during group work, n_0 is the intersection between the graphs of functions f and g.

n₀ is not an intersection. n₀ is a value of n, the input to the function. It represents the value so that any greater value satisfies the condition with c. That sounds very abstract, but n₀ is simply a point along the x axis that you want to be greater than. If you ask what is the n₀ such that x² >= 25 the answer would be n₀ = 5.

Also:

Just to double check my understanding, does function g derive from f? Or are they both independent functions? I feel that it is the former. 

The functions f and g are independently defined. 

And to reiterate:

The running time (in its fullest detail) of an algorithm is represented by theta notation. The worst-case scenario is represented by big-oh notation such that given a function f, f is O(g) if there exists a constant c > 0 and n_0 > 0 where f <= c * g. The best-case scenario is represented by big-omega notation such that given a function f, f is Omega(g) if there exists a constant c > 0 and n_0 > 0 where f >= g/c.

Think of big-Oh as an upper bound and big-Omega as a lower bound. if f = O(g) that means intuitively that f(n) < g(n). It's not quite that simple since it really means that there is some constant c for which f(n) < c*g(n). And it's not quite that simple since f(n) < c*g(n) only when n > n₀. In other words if n is big enough, f(n) < c*g(n).