Big-Oh Notation…

Posted on Updated on

Big-Oh Notation

This idea of an upper bound can be stated more formally. The formal statement of an upper bound is called Big-Oh notation. The Big-Oh refers to the Greek letter Omicron which is  used for expressing upper bounds of overheads of an algorithm.. As computer programmers, our number one concern is how our programs will perform when we have large amounts of data, in this particular case very very large value of n.

As computer programmers, our number one concern is how our programs will perform when we have large amounts of data. In terms of the memory  and CPU time usage of a computer, we wanted to know how our program would perform if we have a very large number of assignments statements to be executed. We found that for second algorithm, all calculations are done  in the same amount of time  irrespective of value of n (n is number of first integers to be added).   Let’s represent the size of the  data set by a variable called n. Let the average performance time for computing sum  of size n be given by f (n). Now one can state the following.

O(g(n)) ={ f |∃d > 0, n0 ∈ Z,  +∋ 0 ≤ f (n) ≤ d *g(n), ∀n ≥ n0 }

In simple English above mathematical statement translates in to:  The class of functions defined by O( g(n)) consists of all functions f, where there exists a d greater than 0 and an n0  (a positive integer) such that 0 is less than or equal to f(n) is less than or equal to d times g(n) for all n greater than or equal to n0.  This behavior is shown as graph in Figure   ……

111

If f is an element of O( g(n)), then  f(n) is O( g(n)). The function g is called an asymptotic upper bound for f in this case. Stated in English the set named O( g(n)) consists of the set of all functions, f(n), that have an upper bound of d* g(n), as n approaches infinity. This is the meaning of the word asymptotic. The idea of an asymptotic bound means that for some small values of n the value of f(n) might be bigger than the value of d* g(n), but once n gets big enough (i.e. bigger than n0 ), then for all bigger n it will always be true that f(n) is less than d* g(n).

Mathematically, if f(n) is O(g(n)), then

However, other way it is not true:

if f(n) is  not O(g(n)),

 

Consider following example  if f(n) = log n,  and g(n) =n , we say log n is O(n) , but n is not O(log n). one can easily prove

The scaling factor d and the threshold n0  are interdependent and differ for different particular functions f(n) in O(g (n)).

  • Notations f(n) = O(g (n)) or f(n) is O( g(n)) mean actually f(n) ∈ O(g (n)).
  • The notation f(n) ∈ O(g (n)) indicates thatf(n) is a member of the set O( g (n)) of functions.
  • All the functions in the set O( g (n)) are increasing with the same or the lesser rate as

g (n) when n → ∞.

Because the time consumed by second algorithm  does not depend on n, the size of the instance, one can say  g(n) = 1.So, the average time to complete the summation for second algorithm  of size n is O(1). If it never takes longer than 1 µs  in second case  in Python, then a good choice for d would be 1. According to the definition above then it must be the case that f(n) is less than or equal to 1 µs once n gets big enough.

Rate  of  Growth

The choice of g(n) = 1 is arbitrary in computing the complexity of an algorithm. One could have taken g(n) = 2. If g(n) = 2 were chosen, d might be taken as  5 instead of 1. But, since we are only concerned with the overall growth in the function g, the choice of 1 or 2 is irrelevant and the simplest function is chosen, in this case O(1). In English, when an operation or program is O(1),  it is said to be  constant time operation or program. This means the operation does not depend on the size of n. This behavior is shown in figure……

The behavior of an algorithm is represented as the  rate of growth of its execution time ( CPU time) as a function of the size of the input problem instance (n). Characterizing an algorithm’s performance in this way is a common practice (an abstraction) that ignores numerous details. To use this measure properly requires an awareness of the details hidden by the abstraction. Every program is run on a computing platform, which is a general term meant to contain:

  • The computer on which the program is run, its CPU, data cache, floating-point unit (FPU), and other on-chip features
  • The programming language in which the program is written, along with the compiler/interpreter and optimization settings for generated code
  • The operating system
  • Other processes being run in the background

Thus changing the platform will change the execution time of the program(an algorithm) by a constant factor. Therefore ignoring platform differences in comparing algorithms with the asymptotically equivalent principle is feasible.

Analysis in the Best, Average, and Worst Cases

One question to ask is whether the results of the previous section will be true for all input problem instances. Most studied algorithms are search and sorting in computer engineering. How will the behavior of different sorting algorithms change with different input problem instances of the same size?

  • The data could contain large runs on elements already in sorted order
  • The input could contain duplicate values
  • Regardless of the size n of the input set, the elements could be drawn from a much      smaller set and contain a significant number of duplicate values

The conclusion to draw is that for many problems, no single optimal algorithm exists. Choosing an algorithm depends on understanding the problem being solved and the underlying probability distribution of the instances likely to be treated, as well as the behavior of the algorithms being considered.

To provide some guidance, algorithms are typically presented with three common cases in mind:

Worst case

Defines a class of problem instances for which an algorithm exhibits its worst runtime behavior. Instead of trying to identify the specific input, algorithm designers typically describe  properties of the input that prevent an algorithm from running efficiently.  For a given program and a given value n, the worst-case execution time is the maximum execution time, where the maximum is taken over all instances of size n.

Best case

Defines a class of problem instances for which an algorithm exhibits its best runtime behavior. For these instances, the algorithm does the least work. In reality, the best case rarely occurs.

Average case

Defines the expected behavior when executing the algorithm on random problem instances. While some instances will require greater time to complete because of some special cases, the vast majority will not. This measure describes the expectation value of CPU time, an average user of the algorithm should have.

Therefore  describing the rate of growth of work or time, we consistently ignore constants. So when we say that  Linear Search of  n elements takes on average:

n +

Comparisions (subject to our earlier assumptions), then by convention subject to these assumptions, we expect  Linear Search algorithm average time complexity to be of O(n).

One can look at ‘Linear Search’ algorithm of a huge list in Python. If the search item is the last in the list, instance size n very large, will have to make n comparisons before computer can find the item.  This will be ‘Worst Case’ scenario. {  O(n), understand why?}.

If the item to be searched is first in the list, CPU will make only one comparison irrespective of value of n. This will be the ‘Best Case’ scenario. The average case will be the arithmetic average of the worst case and best case.   In this case time complexity will be O(n) . Behaviour of O(n) against n is straight line as shown in figure ……

333

For further details contact Vissicomp  26708190 / 9320957718 /17

Written and Edited by

Dr. Ashwin I Mehta

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s