home / homework help / questions and answers / engineering / computer science /

Question

home / homework help / questions and answers / engineering / computer science / prove the following inequality and explain a different ...

Question

Prove the following inequality and explain a different inequality

I looking at the following example:

http://clrs.skanev.com/09/problems/04.html

Question 1:

explain how these are equivalent

Question 2:

show that this is bounded by "n"

Explanation / Answer

Notice that the number of items increases by a factor of 10, but the time increases by a factor of 102. Basically, n=10 and so O(n2) gives us the scaling factor n2 which is 102.

O(n): known as Linear complexity

This time the number of items increases by a factor of 10, and so does the time. n=10 and so O(n)'s scaling factor is 10.

O(1): known as Constant complexity

The number of items is still increasing by a factor of 10, but the scaling factor of O(1) is always 1.

O(log n): known as Logarithmic complexity

The number of computations is only increased by a log of the input value. So in this case, assuming each computation takes 1 second, the log of the input n is the time required, hence log n.

That's the gist of it. They reduce the maths down so it might not be exactly n2 or whatever they say it is, but that'll be the dominating factor in the scaling.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.