How meaningful is the Big-O time complexity of an algorithm?

Posted by james creasy on Programmers See other posts from Programmers or by james creasy
Published on 2013-04-10T23:17:31Z Indexed on 2014/08/18 22:32 UTC
Read the original article Hit count: 440

Filed under:

algorithms

|

algorithm-analysis

|

big-o

Programmers often talk about the time complexity of an algorithm, e.g. O(log n) or O(n^2).

Time complexity classifications are made as the input size goes to infinity, but ironically infinite input size in computation is not used.

Put another way, the classification of an algorithm is based on a situation that algorithm will never be in: where n = infinity.

Also, consider that a polynomial time algorithm where the exponent is huge is just as useless as an exponential time algorithm with tiny base (e.g., 1.00000001^n) is useful.

Given this, how much can I rely on the Big-O time complexity to advise choice of an algorithm?

© Programmers or respective owner

Related posts about algorithms

Finding a problem in some task [closed]

as seen on Programmers - Search for 'Programmers'
Recently I competed in nation wide programming contest finals. Not unexpectedly all problems were algorithmic. I lost (40 points out of 600. Winner got ~300). I know why I lost very well - I don't know how to find actual problem in those obfuscated tasks which are life-blood of every competition.… >>> More
Genetic algorithms

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to implement a genetic algorithm that will calculate the minimum of the Rastrigin functon and I'm having some issues. I need to represent the chromosome as a binary string and as the Rastrigin's function takes a list of numbers as a parameter, how can decode the chromosome to a list of… >>> More
understanding evaluation function

as seen on Programmers - Search for 'Programmers'
I am developing a chess program. And have made use of an alpha beta algorithm and a static evaluation function. I have successfully implemented both but I want to improve the evaluation function by automatically tuning the weights assigned to its features. At this point am totally confused about the… >>> More
How to know whether to create a general system or to hack a solution

as seen on Programmers - Search for 'Programmers'
I'm new to coding , learning it since last year actually. One of my worst habits is the following: Often I'm trying to create a solution that is too big , too complex and doesn't achieve what needs to be achieved, when a hacky kludge can make the fit. One last example was the following (see paste… >>> More
How to implement a genetic algorithm with distance, time, and cost

as seen on Programmers - Search for 'Programmers'
I want to make a solution to find the optimum route of school visit. For example, I want to visit 5 schools (A, B, C, D, E) in my city. Then I must find out what school I should visit first, then the second, then the third etc. with distance, time, and cost criteria. The problem is, I am confused… >>> More

Related posts about algorithm-analysis

Algorithm Analysis tool for java

as seen on Stack Overflow - Search for 'Stack Overflow'
I am looking for an algorithm analysis tool for java that can calculate Big 0 of a function. Ideal I would like to make it part of my build process, along side of my other code metrics tool. Even after searching on google I am unable to find any opensource of commercial tool. Any suggestion would… >>> More
algorithm analysis - orders of growth question

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm studing orders of growth "big oh", "big omega", and "big theta". Since I can't type the little symbols for these I will denote them as follows: ORDER = big oh OMEGA = big omega THETA = big theta For example I'll say n = ORDER(n^2) to mean that the function n is in the order of n^2 (n grows… >>> More
Sublinear Extra Space MergeSort

as seen on Programmers - Search for 'Programmers'
I am reviewing basic algorithms from a book called Algorithms by Robert Sedgewick, and I came across a problem in MergeSort that I am, sad to say, having difficulty solving. The problem is below: Sublinear Extra Space. Develop a merge implementation that reduces that extra space requirement… >>> More
Help with algorithmic complexity in custom merge sort implementation

as seen on Programmers - Search for 'Programmers'
I've got an implementation of the merge sort in C++ using a custom doubly linked list. I'm coming up with a big O complexity of n^2, based on the merge_sort() slice operation. But, from what I've read, this algorithm should be n*log(n), where the log has a base of two. Can someone help me determine… >>> More
How meaningful is the Big-O time complexity of an algorithm?

as seen on Programmers - Search for 'Programmers'
Programmers often talk about the time complexity of an algorithm, e.g. O(log n) or O(n^2). Time complexity classifications are made as the input size goes to infinity, but ironically infinite input size in computation is not used. Put another way, the classification of an algorithm is based on a… >>> More