Focus the growth rate the running time function the input size

Simplifying the Analysis Further

In algorithm analysis, we focus on the growth rate of the running time as a function of the input size n, taking a "big-picture" approach, rather than being bogged down with small details. It is often enough just to know that the running time of an algorithm such as arrayMax, given in Section 1.9.2, grows
proportionally ton, with its true running time being n times a constant factor that depends on the specific computer.

f(n) ≤cg(n), for n ≥ n0.

This definition is often referred to as the "big-Oh" notation, for it is sometimes pronounced as "f(n) is big-Oh of g(n)." Alternatively, we can also say "f(n) is order ofg(n)." (This definition is illustrated in Figure 4.5.)

Example 4.6:The function 8n − 2 isO(n).

Justification: By the big-Oh definition, we need to find a real constant c > 0 and an integer constant n0 ≥ 1 such that 8n − 2 ≤ cn for every integer n ≥ n0. It is easy to see that a possible choice is c = 8 and n0 = 1. Indeed, this is one o f infinitely many choices available because any real number greater than or equal to 8 will work for c, and any integer greater than or equal to 1 will work for n 0

The big-Oh notation is used widely to characterize running times and space bounds in terms of some parameter n, which varies from problem to problem, but is always defined as a chosen measure of the "size" of the problem. For example, if we are interested in finding the largest element in an array of integers, as in the arrayMax algorithm, we should let n denote the number of elements of the array. Using the big-Oh notation, we can write the following mathematically precise statement on the running time of algorithm arrayMax for any computer.

230