Expert: Artemus Harper - 11/2/2009

Question
I wanted to evaluate an algorithm and my adviser told me to use the Big O notation. I really don't know how to use and how to determine using the Big O notation if an algorithm is a good one or not.
How will I evaluate the algorithm? Is it by statement?class? method?

Please help me on these. Thanks a lot.

Answer
Your processor can probably help you better than I can.

The Big O of an algorithm is a calculation of how many steps an algorithm takes in relation to its input size...

Big O of 1: constant time. The algorithm always runs within a certain time regardless of the input size. E.g. An algorithm that determines if the input word starts with a capitol letter.

Big O of n: linear time. If the input size is twice as big, the algorithm will takes about twice as long. E.g. find the biggest number in a list of numbers. A algorithm with a single for loop.

Big O of n squared: If the algorithm takes a second with input size of 10, then it will take 4 seconds with input size of 20, 9 seconds with input size of 30, ect... If you see an algorithm with 2 imbedded for loops, its probably n squared.

Big O of log n: If the input size is twice as big, the algorithm will only take a linear amount of time longer. E.g. a search algorithm to find a number in a sorted list. Start in the middle, and then you know to search higher or lower.

Big O of n log n: A combination of linear time and log n. An algorithm that does a search on a sorted list for every element in the list (for example, trying to find all numbers in a sorted list that have a negative counterpart).

Big O of n factorial (n!): A really slow algorithm.