Posted by: **atri** | September 21, 2010

## Clarification on Q 3 on HW 2

One of you asked about what does it mean for an algorithm to have a running time of ? I’ll talk about this in the lecture tomorrow but I thought it would be good to give some clarification now rather than later.

We say an algorithm has running time of if for *every * and *every* input of size , the algorithm runs for at most steps. In other words, is the maximum number of steps an algorithm can spend on any input of size .

In the above, is an *exact* count. Let us see what this means when we talk about in the asymptotic sense:

- If we say is , then (by the definition of Big-Oh and above) this means that for some absolute constant and large enough , for
*every *input of size , the algorithm uses up *at most* steps.
- If we say is , then this means that for some absolute constant and every large enough , for
*some* input of size , the algorithm makes *at least* steps.

If you have any questions, please use the comments section.

### Like this:

Like Loading...

*Related*

## Leave a Reply