CODEWITHSUNDEEP
algorithmcomplexity-theory
johnnily
johnnily

Reputation: 153

Data structure. f(x) and g(x)

I can understand the run time complexity in the algorithm. But just a bit confuse that when we knew the Algorithm run time complexity is O(n).

we can tell that f(n)< g(n)..

what is g(n) exactly..?

sorry with the rookie question..

thanks.

Upvotes: 0

Views: 200

Answers (2)

Xiao Jia
Xiao Jia

Reputation: 4259

Let f(x) and g(x) be two functions defined on some subset of the real numbers. One writes 

f(x) = O(g(x)) as x -> infinity

if and only if there exists a positive real number M and a real number x0 such that 

|f(x)| <= M |g(x)| for all x > x0

In general, f(x) is the real cost (e.g. number of execution steps) of an algorithm on input scale of x, while g(x) is much simpler than f(x) which can be used to characterize the complexity behavior of f(x).

Upvotes: 1

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

I agree with the comment that f(x) and g(x) are just a pair of functions. f(x) = O(g(x)) tells us they are related in a particular way.

The way this is often used is to make f(x) some complicated, difficult to characterize, function. g(x) is a much simpler function. Knowing f(x) = O(g(x)) gives us a feeling for bounds on f(x) as x increases.

The application to computer science is to make f(x) a measure of program behavior as a function of an input size x. For example, f(x) might be the maximum number of comparisons in sorting an x element array, or the number of words of memory used in some algorithm. f(x) will often be quite messy.

We can make things simpler by finding a nice, clean function g(x) such that we can prove f(x) = O(g(x)).

For example, some algorithm might really take the larger of 35 operations or 10 operations per element in its input for inputs less than size 30, or 1000 operations per element for all larger inputs.

It is much simpler, and easier to compare algorithms, if we just notice that f(x) = O(x).

Note that this is not the same as saying f(x) < g(x). In my example, for large x, f(x) is a thousand times g(x). It just means that g(x) captures how f(x) behaves as x becomes large.

Upvotes: 0

Related Questions