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.

Week after midterm and assigment

As the class thins and tutorial quizzes are not picked up, I wonder whether they know something I should know.

The class is interesting but sometimes a bit confusing. It was interesting how limits could be described symbolically illustrates the difference the position of the quantifiers make. However, it was just one example which took the entire class. I think I would have been better off with short examples such as the one that was asked on the midterm. More than one example cements your understanding but there was no time for a second one.

Now we will go into direct proofs. Not sure what to do there yet.

One of the most difficult things I find in the course are the Venn diagrams. Those dealing with universals are much easier than those dealing with existentials. The problem with existentials is that you cannot pin them down anywhere you can just say that the only sure thing you know is that there are some in a certain area. There are fleeting entities. You can be sure some are in an area but what about elsewhere.

Universals are much easier. You can pin them down to only certain areas. In this way you can definitely say whether expressions are valid or invalid. Just point where one is and the other is not. Even with expressions difficult to pin down one cam always De Morgan them or apply some other transformation. p->Q is an example. It is much easier to treat this as ~PvQ on a Venn diagram.

The way to deal with existentials 'seems' to be by showing counter examples to the expressions. This may make sense from a conceptual point of view but when you actually doing it  feels like cheating. One comes up with one's own conditions - one encapsulates the universe by coming up with a set that helps one give an answer to the problem of validity. One is always left with the thought: "Am I being honest about the set I am creating or is it just a set of convenience"

How to get this is by practice

The only way to get this, unless your mind works this way, is to do exercise after exercise and then look at the solutions. It is difficult to get good at this by just the labs and the assignments, At the labs there are usually about 10 questions to practice on. Our instructor has at best time for half of them. So we do not have even an answer sheet for the rest to know whether we did them right.

The best way to help students is to provide more practice questions. It would also be useful to set aside a target maximum time per question in labs.

Lab1 - What does "not some" or "not all" mean

some should be understood as more than 0. Even 1 is a some.

not some means the same as none

not all means some or none

How to make a statement a false version (negation) in Lab 1

Just add a "not" at the front of the sentence. For instance:

"Some of the three python programs pass all three test suites"

can be made false by adding not at the front as in:

"Not some of the three python programs pass all test suites"

This is easy to understand since "not some" means "none"