Geek Answers Handbook

Algorithm efficiency

So this is a question in my homework ....

Given that the efficiency of the algorithm is n 3 if the step in the algorithm takes 1 ns (10 -9 ) seconds), how long does it take for an input processing algorithm of size 1000?

Here is my question: how do I understand this? PLEASE DO NOT PROVIDE ANSWER. Help me find out how to understand this for myself.

+7
source share
2 answers

You define n as 1000 . Thus, you will need steps n 3 each of which takes 1 ns . Multiply two and you have the answer.

General idea: if an algorithm requires f(n) number of steps and one step takes t , then you need t * f(n) for the algorithm.

+9
source

n in n^3 refers to the size of the data in this case. If you have an input of size 1, paste it into n ^ 3. (and then multiply it by the time.) If you have an input of size 1000 ... what should you do?

EDIT: I originally posted this in a Big-Oh note (e.g. O(n^3) ), which was erroneous as it ignores possible fixed costs that will make the question inconclusive as published. I feel that I should leave this answer, perhaps mainly as a reminder to others, so as not to make the same mistake as me. Thanks for the comment.

+2
source

More articles:


All Articles