4
$\begingroup$

The main question is, how exactly is the big O analysis calculated on routines? Is there a specific formula that relates what each function in a program does to a big O calculation?

Also, what about more complex iterations, such as colour conversions etc?

I would like to point out that this is not a homework question, rather, it is a question from my own research/programming learning curve. I have code that I am working on, but would like to know how this analysis is carried out.

$\endgroup$
2
$\begingroup$

There is no specific formula for calculating it as jmite already mentioned. You have to realize that $\mathcal{O}$ notation serves to merely estimate the number of cycles a certain process takes to execute. It's not an exact representation or quantity.

For instance, lets say you had the following function:

int add(int a, int b)
{
  return a+b;
}

This function would be $O(1)$ because it is a linear operation. There are no loops, tree or list traversals (if you've gotten up to those topics already), etc. It's a simple single instruction function.

Now if I modified that function to say the following

int redundantAdd(int a, int b)
{
  int c = a+b;
  c += 0;
  b+= c;
  return c;
}

you'll notice that I now have 3 more instructions than the previous snippet. However, it is still $O(1)$. Again, we are just trying to give a general idea of the amount of time spent on a process, not an exact number.

Now suppose I created another function, like the one below.

int summation(int array[])
{
  int sum = 0;
  for(int i = 0; i < (sizeof array)/(sizeof array[0]); ++i)
  {
    sum += array[i];
  }
}

This block of code is now $O(\text{length of array})$ (we say $O(n)$ if the array length is $n$), since we are generally executing $n$ number of tasks. We do not take into consideration the initialization of sum at the beginning. It's usually insignificant unless $n$ is small.

Now suppose I modified that code to add all the elements in a matrix

    int summation(int matrix[][], int width, int height)
    {
      int sum = 0;
      for(int i = 0; i < width; ++i)
      {
        for(int j = 0; j < height; ++j)
         {
            sum += matrix[i][j];
         }
      }
    }

This time we have $O(n^2)$ if if the width == height = n , we essentially iterate through the loop $n^2$ times. Again, we're only estimating here, so we don't care if they're different, it just makes for easy representation. I won't bother you with logarithmic big-O notation yet as you need to drill down on the key purpose of the notation first. Doing so will only confuse you.

$\endgroup$
  • $\begingroup$ Okay, I do understand what you are saying here - it makes perfect sense to me. Thank you. Feel free to 'bother' me with logarithmic big O notation as well (if you have time). $\endgroup$ – user8872 Jun 28 '13 at 3:07
  • $\begingroup$ Sorry for the late response, I'm not on here often. Anyway, look up "binary search tree" on Wikipedia and get familiar with it if you're not already, then continue reading the next comment. $\endgroup$ – audiFanatic Jul 11 '13 at 22:44
  • $\begingroup$ Now that you know what a binary search tree (BST) is, logarithmic big-O notation is quite simple. Basically, imagine if you have a set of nodes in a BST. Remember that a BST has all nodes less than the current node to the left, greater than to the right (I believe equal to is up the coder if I remember right). So let's say you're looking for a number. Now you don't have to iterate through the entire unsorted set to find what you're looking for (which would be O(n) as we saw before. Now you know where to search starting at the root. $\endgroup$ – audiFanatic Jul 11 '13 at 22:49
  • $\begingroup$ So if you're looking for the number 2 and your root node is, say 10, you know the number 1 is to the left of 10 and cannot be right of it. So now you've just eliminated a good portion of the numbers you need to search through to find your number. Now come the logs. Remember back to high school. A log is basically asking "the base to what power equals a number n?" Since we're using a binary tree, we can estimate the number of nodes in the tree by its height h. 2^h ~= number of nodes n. So if we want to know how many comparisons we need to make, we do log_2(n) , which is roughly the height. $\endgroup$ – audiFanatic Jul 11 '13 at 22:58
  • $\begingroup$ And there you have it. Get a good book on graph theory if you're interested in these computations with data structures like trees (there are many more other than binary trees). $\endgroup$ – audiFanatic Jul 11 '13 at 23:01
3
$\begingroup$

There is no such formula. If there were, it would solve the halting problem, because we could take an algorithm (Turing machine), find its big-$\Theta$ complexity, then return true or false depending on if it was $\Theta (\infty)$.

For Big-O (upper bounds), there's technically a formula, since all functions are in $O(\infty)$. However, there's no way to find a tight upper bound, nor to test if an algorithm has a bound tighter than $O(\infty)$.

That said, there are certainly tools and heuristics for determining these things, as well as limited models of computation for which the problem is decidable.

For example, if you can express your routine using recursion, often you can find a recurrence relation for the running time, which you can solve to find the Big-O time. However, none of these techniques will work all the time.

$\endgroup$
  • $\begingroup$ afaik, any algorithm can be expressed using recursion and conditional execution, so this part of your reasoning is wrong. the correct answer should be that in most cases we can't statically compute recursion depth $\endgroup$ – Bulat Jun 30 '13 at 14:16
  • $\begingroup$ I just shortly want to mention that jmite's argument does not backup his proposition. Any complexity one could think of (if we consider functions $f: \mathbb{N} \to \mathbb{R}$) is in $\mathcal{O}(\infty)$, because the $\mathcal{O}$-notation just talks about upper limits of functions. The formally correct question to ask is whether or not "$\infty \in \mathcal{O}(f)$?" for $f$ being the function describing the Turing Machine's runtime. $\endgroup$ – Rmn Jul 17 '13 at 9:31
  • $\begingroup$ Edited to reflect this. $\endgroup$ – jmite Jul 17 '13 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy