I missed the class where big-O was introduced thinking that it was pretty straight forward. It still seems to be however the teacher said something about O(n) deviating from the function when n gets very small? I couldn't find this anywhere in the book. Could someone enlighten me? Our exploration of O(n) has been in the context of sorting algorithms if that is of any significance.

Thanks Gene

edit: Thanks for the help guys it has been illuminating. I have a follow-up question. Is there a relatively simple mathematical way to figure out the point where n is too small for O(n)?

Related questionsare there any O(1/n) algorithms?

What is the difference between Θ(n) and O(n)?

Big O doesn't describe the execution time of a function, just the growth. All functions have some constant factor or overhead that needs to be added in. When n is low, this overhead can greatly dwarf any improvements to the algorithm - an algorithm that requires 50ms per operation but has O(n) will perform worse for small n than an algorithm that requires 5 ms per operation, but has O(n*n).

This is why, in general, for small sets big O doesn't matter. For most objects with simple comparisons, a quick sort on 10 items will not be noticiably faster than a bubble sort, a linear search on 100 items will probably be faster than a binary tree, and so on.

The course material gets harder to understand as the number of lectures attended (N) becomes very small.

Maybe the following is an example of "O(n) deviating from the function when n gets very small":

Consider an operation which requires, for example, time "50 times n, plus n squared".

When n is large then the "n squared" term will dominate, and so the operation can be said to be "O(n squared)".

When n is small, however, the "n squared" term will be negligible, and the "50 times n" term will dominate, and so when (and only when) n is small then it could be said to be O(n).

To expand on the answer above, Big-Oh notation measures the eventual growth of the function or its limiting behavior.

f = O(g) if and only there exists an N and a constant c (which can be a function of N) such that for all n > N,

f(n) <= c*g(n)

Lets say f = 10000000*n and g = n^2.

f = O(g), however if you look at too small values of n, say less than 10000000 and set c = 1, you will see that g(n) <= f(n).

To add a more extreme example, would you rather deal with an algorithm with complexity n^100000 or an algorithm with complexity of 2^(.0000000001n). For reasonable problem sizes, the latter is better. What makes a lot of CS so beautiful is that it allows for this type of abuse, however, most natural algorithms do not take advantage of it. Most polynomial time algorithms have small constants (at least after a little of work).

Good luck!

The concept behind Big-O notation is the asymptotic performance of the algorithm. As N gets bigger, the term in the Big-O notation comes to dominate the total time. For example, in an O(N^2) algorithm, the total time T(N) might be:

```
T(N) = a * N * N + b * N + c
```

As N gets bigger, and bigger, the term in N^2 dominates, regardless of the value of b or c.

When N is small, though, the b and c terms matter.

For example, if a = 0.001, b = 1,000, and c = 1,000,000.

```
N ~ T(N) [1 significant figure]
1 1,000,000 (almost all c)
1,000 2,000,000 (50:50 split on b and c)
1,000,000 2,000,000,000 (50:50 split on a and b)
1,000,000,000 1,000,000,000,000,000 (almost all a)
```

So, if you ignored the low-order terms, the performance at low N would be completely misrepresented. At high N, the low-order terms don't matter.

A big off topic but for the sake of completeness I want to mention some other notations which are related to the Big_o notation and commonly used in theoretical computer science and which you may find referred to in computer science literature: The Big-Θ notation, the Big-Ω notation and the little-o notation. These are simply other (and tighter) descriptions of growth rates. The little-o notation is easily mistaken for the big-O notation.

The little-o is also a relation between two functions f(x) and g(x). Saying that 'f(x) is little-o of g(x)' means that f(x) grows much faster than g(x). In more mathematical tearms is says that the limit of f(x)/g(x) is zero, as x approaches infinity.

As mentioned in the previous answers the big-O notation is used to describe the upper bound of the growth rate of an algorithm. It is really a relation between two functions f(x) and g(x), where f(x) = O(g(x)) as x goes to infinity.

See the Big-o wikipedia page for a nice and concise presentation of the different notations.

According to the definition:

f(n)=**Θ(g(n))** means the **set of** all the **functions f(n)** such that there needs to be constants **c1** and **c2** and **also n0** where all of these cases are **true**:

*c1 . g(n)*is a non-negative term or 0.*c1 . g(n) <= f(n)*[g(n) needs to be the lower bound for certain n]*f(n) <= c2 . g(n)*[g(n) needs to be the upper bound too since we are defining Θ].- for all
**n greater than our selected n0**

So all we need to do is select such a c1, c2 and n0 that makes ALL the conditions true. Therefore for certain combinations of c1 c2, if you select n < n0, you cannot guarantee that your bound works. I think this is what your teacher meant by "the deviation".

Similar Questions

If exists, I need to remove \r\n\r\n at the very beginning and/or at the very end of string. My issue is I couldn't achieve my aim with codes below. //if exists, remove \r\n\r\n at the very beginning

I having a weird problem with a DAO class and a StoredProcedure, what is happening is that I use a CallableStatement object which takes 15 IN parameters, the value of the field id_color is retrieved c

The result of expression: 2.227E-19-1.0+1.0 would be 0.0 How can I get result of 2.227E-19 ? I have an expression a-b+1 and a always be a very small number. b might be close to 1.0 HOW to keep ac

I am writing a cookie for auto login users. It works almost flaw less. But when the Session times out the cookie gets deleted, although it's set for 30 days. I can't understand why this is happening.

Often, when a lot of applications were opened before my application I get didReceiveMemoryWarning and then, after a while iOS usually closes my application. This is actually become a noticeable prob

I'm solving some recurrence relation problems for Big O. T(n) = T(n-1) I started with: T(n) = T(n-1) T(n-1) = T(n-2) .. T(n) = T(n-k) Now setting k to n-1 T(n) = T(1) So the result is T(n) = O(1)

I have two arrays in float64 type and when I assign the value of the first to the second it rounds the value. The following simple code illustrates the problem and excludes the possibility of just a m

I have 6 images, all the same size (65x65). When I create an imageview and add this image through the image view attributes in the interface builder, the picture is very small. Maybe 5x5. The pictur

I am having an issue with a query where the query plan says that 15% of the execution cost is for one table. However, this table is very small (only 9 rows). Clearly there is a problem if the smallest

function foo() { console.log(clicked); } element.addEventListener(click, foo()); Why does foo() gets selfinvoked when the script loads and foo doesn't? And what if I need to pass an argument to t

Is it possible when debugging to set a watch on a property or variable, and then have the debugger highlight the line where the value is changed. I've had a situation where I spent ages going through

I read this answer which made it sound like when a shared value is evaluated, it is only evaluated once and then the result is stored. For example: x = 2 + 2 y = 2 + x z = 3 + x Here, x is evaluated

I need to implement a very efficient method of checking if a certain key (long value) is present in a small collection of items (less than 100, usually around 10) in java. This check must be as effici

I need to distribute a large integer budget randomly among a small array with n elements, so that all elements in the array will have the same distribution and sum up to budget and each element in the

I have this problem, I store a number in a database field. After a while I check if a value exist and if it does I take the number and add 1 this works fine up until 10, when I add a number to 10 it g

Is there anyway I can add items to a TreeView control just when a node gets expanded? I'd like to add child items to a tree item when the users expands the parent item.

The code below produces a cell array containing n (=210) 2x3x4-shaped n-d arrays. n = prod(5:7); makendarray = @(i) reshape(1:24, 2:4) + (i * 1000); ndarrays = cellfun(makendarray, num2cell(1:n), 'un'

Data labels (in this case cash) appear in the right place, just inside the bar on the right, most of the time. However if the value of the bar is low enough, it ends up overlapping with the axis label

I want to make the textfield expand when the text nearly gets to the end, it works but when i type the first letter in it shrinks and then it expands i.e http://jsfiddle.net/Y3rMM/ How can i keep the

import scala.tools.nsc._ import scala.tools.nsc.interpreter._ val settings = new Settings val n = new IMain(settings) n.interpret( val y = 5 val x = 10 ) println(n.valueOfTerm(y).get) n.close(

I want to create a Java method, which accepts an inputArray = Object[n][], where n can be any integer, and outputs a list of possible n-size combinations between all values of the n subarrays. Below i

I'm trying to write a very simple ruby script that opens a text file, removes the \n from the end of lines UNLESS the line starts with a non-alphabetic character OR the line itself is blank (\n). The

I want to generate all permutations of an n by n list with max value n-1, for example, for n=3, all the possible lists are as follows [0,0,0] [0,0,1] [0,0,2] [0,1,0] [0,1,1] [0,1,2] [0,2,0] ... [2,2,2

This question looks simple to me, but just wanted to see whether i am moving in the right direction. Is it as simple as saying when n =1 ??

I'm trying to compute the log of the mean of some very small values. For the current data set, the extreme points are log_a=-1.6430e+03; log_b=-3.8278e+03; So in effect I want to compute (a+b) / 2, o

I am trying to compute factorial of large numbers mod a large prime number. arr[] stores the value of the factorials for various numbers If I calculate fact(32570) first and then print arr[1] and arr[

I have a weird behavior with XElement. It seems the Value property changes the new line expression \r\n to the unix like expression \n. Why is that? string valueString = abc\r\ndef; string xmlString

I noticed that frequency tables created by data.table in R seem not to distinguish between very small numbers and zero? Can I change this behavior or is this a bug? Reproducible example: >library(

I need to add a very small value to a floating point value to make it insignificantly different so that it fails an equality test. To avoid issues with precision, instead of adding a very small number

T (1) = c T (n) = T (n/2) + dn How would I determine BigO of this quickly?

If redis gets overloaded, can I configure it to drop set requests? I have an application where data is updated in real time (10-15 times a second per item) for a large number of items. The values are

I set my cookie with PHP like this: setcookie( hero, , Comma . Dot < Left > Right - Dash _Underline / Slash \\ Backslash, time() + (10 * 365 * 24 * 60 * 60)); But somehow, this is the value

What is the BigO complexity of following lgorithms: boolean intersection(TreeSet<?> set1, TreeSet<?> set1){ if(set1.size() > set2.size()){ return intersection(set2, set1); } for (Object

Ok, these are all pretty simple methods, and there are a few of them, so I didnt want to just create multiple questions when they are all the same thing. BigO is my weakness. I just cant figure out ho

I'm using CPLEX in C++ to solve a hub location problem, a MIP, and I've recently found a very precise set of inputs that CPLEX thinks is infeasible (i.e. CPXMIP_INFEASIBLE) even though the problem is

Below are two schema which I believe achieve the same result, i.e. m:n relationship with the option for a default/preferred value. Is there any reason to use one over the other? Schema #1 CREATE TABLE

I'm having trouble getting the data in a DataTable to show up in a GridView. When I use the code below to set the ItemsSource to the Default view for the DataTable I've populated, nothing seems to get

Let's imagine that we have some couchbase bucket containing N docs, each S bytes size and V views count. We need to retreive those docs incl. all info that they contain. One way: Create a view that ha

Value was either too large or too small for a Decimal error is displaying when i convert to decimal code is below. decimal tempValues = 0; Value1 = 0.0 Value2 = 0.0 tempValues = Convert.ToDecimal(Valu

Here is my code: #include<stdio.h> #include<stdlib.h> int main(){ int a,b,c; printf(Enter the numbers:\n); scanf(%d %d %d, &a,&b,&c); printf(%d %d %d,a,b,c); return 0; }

I want to check a #N/A value into excel with VBA. So after some research, I made this code : Set MyTab = Range(name) If (Not IsEmpty(MyTab.value)) And (MyTab(i, j).value <> CVErr(xlErrNA)) Then

When I use my application for awhile, I have noticed that the device gets hot. Apple devices usually get hot when running applications, so I want to know if there's a method to check if I have done so

I'm new in ios development.I want to stop the avaudiorecorder when duration gets 5 mins.How to stop the avaudiorecorder automatically the duration gets over. How to do this.

I have a dataGrid that iterates a list of object. In each grid I have a commandButton and a tag that tries to put the Id of the object selected in the backing bean, but when action is executed, and al

How do I specify zoom level for google maps in a kml file or why is it that my zoom level gets over ridden when I load this file. My question is actually how do I control zoom of a map for the followi

I have created some code for my unity game. When my player reaches a certain distance to my enemy the enemy goes from idle to run and then when it gets within a closer distance it switches to the atta

I have a text area in a form im writing pasting the comma separated value in the text area like 1,2,3,4,5 6,7,8,9,10 11,12,13,14,15 when i submit from its creating a csv file but the csv file in the

I've got this problem, I have a java file that obtains 2 variables from another file and is supposed to add them together and return the summed value. So far it works on obtaining the values aFirst an

I have an experimental winform which is tiny: 20 lines of added code two controls datagridview a small Sql Server Compact db included - with a table containing 3 rows of data When I launch the .appl

I am making a web app. In one part, I have a checklist dynamically generated with javascript. I want to have a jQuery function executed when the checklist is checked. Here is the code that dynamically