Not Yet Answered # Big O notation

Teme64 215 Teme64 215 cgeier 187 Discussion Starter overwraith 57 Teme64 215 sepp2k 378

0

I think almost every computer science book has it. Especially books about algorithms. You could try to find some online course material about algorithms. Check also Wikipedia.

HTH

0

Wikipedia had a **really** professional explanation about ordo i.e. I didn't understand the math :) But check the references and external links which this article has.

0

Also search for "data structures" or "data structures and algorithms". Here's a url that showed up: https://www.cs.auckland.ac.nz/~jmor159/PLDS210/searching.html

0

Ok, thanks. None of the school cirriculum books I have read broach the topic. I heard it mentioned in a C class but never substantially. I have had some Calculus classes, so I will understand some of the math, but honestly people just don't know how to teach math these days. From what I understand as a variable approaches infinity the algorithim will tend to reflect some of the features of a certain function, some terms will be dropped, and some will become more dominant. So algorithims can be evaluated for efficiency by attributing certain functions to them.

0

a variable approaches infinity

You're right and that 'variable' is the number of elements. For example sorting algorithms are a well studied area of algorithms. Given N elements to sort, Bubble sort is an O(N x N) algorithm while Quick sort is an O(N x log(N)) algorithm.

some terms will be dropped

Ordo notation removes any constant factor from the algorithm. For example you could have an algorithm which takes 3xN operations and second algorithm which takes 70xN operations for N elements. Former algorithm would be more efficient in practise but in theory both are O(N) algorithms i.e. equally 'efficient' theoretically.

HTH

*Edited 1 Year Ago by Teme64*: Edited formatting

0

You're right and that 'variable' is the number of elements.

That variable is whatever you say it is. In the context of computer science it's usually the size of the input, but it could be anything as long as you make that clear. For example it's very common to express the complexity of graph algorithm in terms of two separate variables: the number of nodes and the number of edges.

Ordo notation removes any constant factor from the algorithm.

As well as constant summands, but that's not all. For example 3x^2+2x+1 is in O(x^2), so you don't just drop the constant factors and summands, you also drop any term t such that the limit of `t/f(x)`

is 0.

Of course the function you're trying to classify may not be a simple sum of terms at all, so the dropping-constants-and-smaller-terms approach is just a rule of thumb.

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

I don’t want at this stage work on a big separate project as I've already got plenty ...

I am writing a java program that needs to execute shell commands, so I wrote a function that would take the command to execute as a string (ie: "mkdir ~/Folder1") and execute that command with the shell. Here is the function:

```
try
{
Runtime run = Runtime.getRuntime();
Process pr = ...
```

Hi. I have a form with list box : lst_product, datagridview : grd_order and button: btn_addline. lst_product has a list of product ids selected from database (MS Acess 2013) , grd_order is by default empty except for 2 headers and btn_addline adds rows to grd_order.

btn_addline :

`Private Sub btn_addline_Click(ByVal ...`