Figuring out the upper bound of an algorithm with multiple embedded for-loops
Pages: 12
out what big-Oh set the algorithm belongs to isn't that hard.
Please do not be fooled by this.
If you think Big-O is easy, try to figure out the big-O for the sequences given on the shell sort wiki page and get back to me. Many, many functions fall into a very small subset of answers, and this is natural, and it is good. But many other algorithms have very odd run times that are extremely challenging to unravel.
commonly, you see N*N, lg(N), (1), and intractables (anything worse than N*N is intractable for N of any real big size, such as N! or N^N or the like). Shell sort gives a lot of N*C/K where C>K eg 7/6. And getting there takes 2-3 pages of analysis. Recognizing the top 3 results (and when its not one of those!) becomes easy with practice, though.
Point is, finding big-O is *usually* easy and once in a while, its quite difficult.
Please do not be fooled by this.
If you think Big-O is easy, try to figure out the big-O for the sequences given on the shell sort wiki page and get back to me. Many, many functions fall into a very small subset of answers, and this is natural, and it is good. But many other algorithms have very odd run times that are extremely challenging to unravel.
commonly, you see N*N, lg(N), (1), and intractables (anything worse than N*N is intractable for N of any real big size, such as N! or N^N or the like). Shell sort gives a lot of N*C/K where C>K eg 7/6. And getting there takes 2-3 pages of analysis. Recognizing the top 3 results (and when its not one of those!) becomes easy with practice, though.
Point is, finding big-O is *usually* easy and once in a while, its quite difficult.
Last edited on
I agree, but in school/uni, unless you're going into more masters/doc-level stuff in Computer Science, chances are you won't have to deal with complexities outside the normal polynomial or log w/ polynomial types.
Hah, I fogot NlgN in the list, so 4 common ones, or as you said, various polynomial combinations of the 3.
I have never had to deal with it period. After school, almost everything is a known algorithm or a minor modification of a known one and someone already did this and told you the answer (all you care about in industry). It takes some pretty hard core R&D or 'out there' task to have something totally new and to get something that isnt one of the common answers.
I have never had to deal with it period. After school, almost everything is a known algorithm or a minor modification of a known one and someone already did this and told you the answer (all you care about in industry). It takes some pretty hard core R&D or 'out there' task to have something totally new and to get something that isnt one of the common answers.
Topic archived. No new replies allowed.
Pages: 12