OU blog

Personal Blogs

Valentin Fadeev

Big O-Oh

Sunday, 11 Apr 2010, 23:37
Visible to anyone in the world
Edited by Valentin Fadeev, Sunday, 16 Jan 2011, 23:17

There are many good articles on O symbols, some more technical, some more popular. But at the end of the day you often find yourself staring at the excercise remembering all those definitions and still not knowing what to do next. This has been the case for me, until i took some freedom to play around with this device. I think i finally got it down. Here are two examples:

x1/2/(1+O(x))=x1/2(1+O(x))=x1/2+x1/2O(x)=O(x1/2)+O(x3/2)

=O(x1/2)+O(x1/2)=2O(x1/2)=O(x1/2)

Where in the first equality i used geometric expansion until the linear term and the fact that for non-zero k kO(x)=O(x), hence -O(x)=O(x). Of course "=" sign must be understood as element of through all manipulations with O.

A more demanding one:

equation sequence two times phi minus sine of two times phi divided by two times sine squared of phi equals sum with, 3 , summands two times phi minus two times phi plus eight divided by six times phi cubed plus cap o of phi super five divided by two left parenthesis phi plus cap o of phi cubed times right parenthesis squared equals four divided by three times phi cubed plus cap o of phi super five divided by two times open sum with, 3 , summands phi squared plus cap o of phi super four plus cap o of phi super six close equals

equation sequence equals four divided by three times phi cubed plus cap o of phi super five divided by two times open phi squared plus cap o of phi super four close equals two divided by three times phi times one plus cap o of phi squared divided by one plus cap o of phi squared right parenthesis equals two divided by three times phi times open one plus cap o of phi squared close times open one plus cap o of phi squared close equals

equation sequence equals two divided by three times phi times open sum with, 3 , summands one plus cap o of phi squared plus cap o of phi super four close equals two divided by three times phi times open one plus cap o of phi squared close equals two divided by three times phi plus cap o of phi cubed

Of course, it would be a bad idea in the 5th transition to cancel out the numerator and denominator simply by division. The two O-s in this case may stand for different classes of functions.

Tags: m820, o-notation, asymptotics
Permalink
Share post

This blog might contain posts that are only visible to logged-in users, or where only logged-in users can comment. If you have an account on the system, please log in for full access.

Total visits to this blog: 77427