Relationship between limit value, big-Oh, big-Omega, and big-Omicron

Sometimes a theorem is so simple that we do not think about it much. The answer to the limit between f and g says quite a bit. I found this while trying to understand it for use in the assignment:

Let f(n) and g(n) be functions such that

lim    f(n)/g(n)= A.

x -> infinity

1. If A = 0, then f(n) = O(g(n)), and f(n) <> Omicron(g(n)).

 

2. If A = 1, then f(n) = Omega(g(n)), and f(n) <> Omicron(g(n)).

3. If A is finite, but not 0, then f(n) = Omicron(g(n))

Simple but not obvious

Alternative to annotated slides not available on cdf

This has been a frustrating week. Not able to download the assignment, as well as no access to notes on the website. Now we have the assignment but no notes. This is a difficult situation. To get around it I searched for notes from other universities or websites, Actually, one of them has an answer to one of the questions (Bonus!). I decoded to list them for others to use:

Big-Oh summary with limits from University of Nebrasca:

http://cse.unl.edu/~choueiry/S06-235/files/Introduction-HandoutNoNotes.pdf


Asymptotic Growth Rates from University of Guelph posted on UBC website:

https://www.cs.ubc.ca/wccce/Program03/papers/Obi2.pdf

Asymptotic Notations from University of Illinois.(Obama I think taught there). Theoretical stuff but good stuff on logs:

http://www.math.uiuc.edu/~hildebr/595ama/ama-ch1.pdf

Growth of Functions from Dartmouth:

http://www.cs.dartmouth.edu/~ac/Teach/CS19-Winter06/SlidesAndNotes/CLRS-3.1.pdf

Big O Notation from Ryerson - short overview:

http://www.scs.ryerson.ca/~mth110/Handouts/PD/bigO.pdf

That is it for now!

What is big-o

I think it is interesting how csc148 and csc165 are converging. This gives one a better sense of how big-oh is used. Algorithms are an essential part of computer science. With big-oh it is possible to determine which algorithm is best without having to actually run the code. Sort and  tree search algorithms are two examples that can be evaluated in this way.

The function f  as a member of big-O just says that f is a function that does not grow faster than a function g times a constant multiplier (c); for a for numbers greater that a certain breakpoint (B). In simple terms, for n>no, f(n) tracks cg(n).

Knowing this, there are two possibilities for an algorithm: f(n) either tracks c(g(n) or it does not. One has to either prove or disprove this.

To prove, it must be shown to be f(n) <= cg(n), for a set of conditions c and B. To disprove, one must prove the negation of the statement. One must find an instance of n as a function of c and B for which the negation is valid.

Simple to say, not so easy to do.

The logic course is coming together with computer science. Actually, CSC165 is now related to CSC148. In the lab, we began to look at the time different approaches to trees take during a sort. We timed these different approaches and concluded that insertions take much longer than recursion.

In CSC165 we have been looking at for loops but I imagine that soon we will look at recursion. We will then calculate the ceiling and floor a set of code takes.

Frustrating assignment

I believe that my partner an I finished the assignment. For the most part we believe that the proofs are well formed. That the conclusion follow the statements presented. However, studying for the midterm I looked at books in order to get some extra questions to prepare. What I noticed was that each author has a different structure to the proof. The components necessary to construct a formal proof are there but the presentation is very different. I is not clear that there exists an accepted structure to proofs that most, if not all follow.

So knowing this, I wonder what is right? Do different TA's bring a different perception of what a good proof is? I am sure that an answer sheet is provided but it is unlikely that all students will have the exact same proof structure.

For instance, should a variable include a subscript when it is being instantiated? Even in this course, some have them, some do not. It is difficult to decide - so I guess to be safe we should include them.

How to deal with x + y in floor proofs

During my trying to do assignment 2, I stumbled into a nice way of restating stuff like x + y. Actually y can be a variable or an integer. The following is just a sketch that can prove useful; it assumes y is a variable:

To make it easier, [x] means floor of x

x + y = x  + [x] -[x] + y + [y] - [y]

= x-{x}+ y - {y] + [x] + [y] 

but x - [x] < 1. the same for y (from class notes)

Therefore: x + y < [x] +[y] + 2

How is this useful?

Thy this on the limit proof on the assignment to set d as a function of epsilon.

Post midterm

One of the things that I find frustrating is the typing of the symbols. Latex has too much overhead for a slow typist. Word can be adapted to get all the symbols but it usually takes a lot of cut and paste. However, I found a new way. One can set up symbol shortcuts using ctrl and alt keys. This has helped me a lot lately.

A post midterm topic are mathematical proofs. I still do not get the limit proof. This is the second time it has been presented but I cannot follow it. The other proof that I find difficult is the prime number one. I need to study both much more closely. Perhaps using external sources.