This website will be unavailable from 05:00 (for up to 4 hours) for scheduled maintenance.
Due to scheduled maintenance, this website may become unavailable at any moment.
Personal Blogs
Personal Blogs
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:
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 through all manipulations with O.
A more demanding one:
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.
Big O-Oh
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 through all manipulations with O.
A more demanding one:
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.