| |
You are here: Experts > Computing/Technology > Focus on Java > Java > Big O Notation problem
Java - Big O Notation problem
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.
Add to this Answer Ask a Question
|
|
