3 ms·

>It is designed to estimate the amount of time it takes to run an algorithm using a data structure like a linked list instead of a different one like a binary t

>It is designed to estimate the amount of time it takes to run an algorithm using a data structure like a linked list instead of a different one like a binary tree. Wat?? Excuse me, but it seems you have no idea what you're talking about. >Consider this, that you really cannot get a good estimate of how long any algorithm can run because you got other factors in play That has absolutely nothing to do with the complexity of the algorithm. Also, it _can_ be estimated, too. I wonder if you're trolling or just clueless

claudius 13y ago
> I wonder if you're trolling or just clueless Given the curious interpretation of ‘polynomial’ by means of an only somewhat correct translation, I’d tend to the latter.
- orionblastar 13y ago
  Well I admit I don't understand it fully. That is no reason to accuse me of trolling or downvote my comments. http://en.wikipedia.org/wiki/Polynomial http://en.wikipedia.org/wiki/Polynomial Is Wikipedia not correct on this issue? I was told on one hand to look stuff up on Wikipedia, and on another I found out it is not always correct.
  - claudius 13y ago
    ‘poly’ means many, yes, and ‘nomial’ in this context can stand for ‘terms’ or ‘expressions’ (not really numbers, but maybe formulae as you said). However, ‘polynomial’ does not mean ‘many terms’ when used by mathematicians and, in extension, computer scientists. A polynomial function, in this context, means a function that is/can be expressed as a sum of powers (usually restricted to a finite number of addends) of its input variables with appropriate prefactors. For example, f(x) = 1 is a polynomial function, but it certainly does not have many terms (nor numbers). That the finiteness of the sum is an important requirement when it comes to complexity can be seen by the fact that the exponential function can be expressed as an infinite polynomial: exp(x) = 1 + x + 1/2 x² + 1/6 x³ + … In other areas, where people are more concerned with nondivergent or differentiable functions, this requirement is often dropped and nearly everything that doesn’t have poles in x is called ‘polynomial’. Furthermore, you didn’t only get downvoted for misinterpreting polynomial, but also for the strange mixing of theoretical CS, which is concerned with the complexity of algorithms at hand, and real-world effects such as slowdowns due to other programs multitasking, CPU caches etc. etc. which are rarely taken into account when deciding whether a given algorithm is remotely feasible to implement (runs in time, say, n^10 or faster) or just too slow.
    - orionblastar 13y ago
      Ah I see, I am exploring theoretical areas of computer science for which there are no clear answers yet. Downvotes for you, bad HN user for making us try to think of new theories. :) So a Polynomial doesn't need be many of them, it can be just one of them. The poly in the name threw me off I admit. I would have assumed that was a mononomial for just one and two of them are a binomial but apparently polynomial is used instead even for only one or two? I hope you understand my confusion there. Thank you for clearing that up.
      - claudius 13y ago
        Just as poly- and mono- are prefixes of Greek origin[0], you’d probably use ‘di-’ rather than ‘bi-’ here (binomials are a little different, again), just as you have monosaccharides, disaccharides and polysaccharides[1] (aka carbohydrates). The relevant point is that it usually doesn’t matter whether you have one, five or 500 terms in a polynomial, as the largest one will certainly dominate for sufficiently large input sizes[2] and all terms in a polynomial essentially behave the same way (being differentiable, having no poles etc.). [0] The only thing wrong with homosexuality is smashing a Greek prefix onto a Latin root. [1] Latin: uno-, bi-, pauc-, multi-, Greek: mono-, di-, oligo-, poly- [2] cf. http://www.wolframalpha.com/input/?i=x%5E20%3B+x%5E20%2Bx%5E10+for+x+from+100+to+1000 http://www.wolframalpha.com/input/?i=x%5E20%3B+x%5E20%2Bx%5E...
      - nitrogen 13y ago
        Ah I see, I am exploring theoretical areas of computer science for which there are no clear answers yet. Downvotes for you, bad HN user for making us try to think of new theories. :) In science in general, including computer science, "theoretical" doesn't mean fringe or unexplored, it means foundational and abstract. CS theory uses the word "theory" in the same sense as music theory. CS theory deals with well-defined, rigorous analysis of computation in abstract or mathematical terms. I would have assumed that was a mononomial for just one and two of them are a binomial but apparently polynomial is used instead even for only one or two? A two-termed polynomial is also called a binomial. "Binomial" and "monomial" are special cases of the more general term "polynomial".
orionblastar 13y ago
Well I am trying to understand it better. Instead of explaining it to me better, I get downvoted instead. Please explain it further and tell me how you can estimate the time when a DDoS attack is being done on the system, or the CPU is overheating, I'd really like to know how you estimate that. Apparently I'm clueless and in need of many clues.
- gurvinder 13y ago
  With 25 years of experience in computer industry, you should be explaining us all how we can estimate the time when a DDoS attack is being done:). Anyways we are talking here about complexity of the algorithm, and not its actual speed or performance which will depend on a lot of factors. But complexity tells for example how many steps it will take for the algorithm to solve the problem. The algorithm can be used by Humans or super computers, so performance can vary from days to microseconds, but complexity will remain same.
  - orionblastar 13y ago
    I think I covered that in this ebook: http://www.smashwords.com/books/view/314107 http://www.smashwords.com/books/view/314107 :) BTW it is a joke written by MIT's AI SciGen software to show how hard it is to tell if a thesis is serious or a parody written by clever AI software. Even if I mark it as parody and Computer Science Fiction some people are taking it seriously. Even when it says stuff like added 27 25Ghz Intel 386 chips to the network. :) The 386 chip does not run that fast. OK complexity, then why is polynomial time used to describe it? I know some compilers can optimize machine code better than others, how does that affect the complexity? If the performance can vary from days to microseconds, well that is a very big gap. Video gamers always complain about 'lag', and days well that is one heck of a 'lag'! :)
- chc 13y ago
  Your comment was not phrased along the lines of "Can anybody please explain this?" It was phrased as though meant to impart wisdom. That's why it got downvoted and why people are correcting you — because you (apparently) meant to ask a question but ended up making a bunch of erroneous claims instead.

claudius 13y ago

> I wonder if you're trolling or just clueless Given the curious interpretation of ‘polynomial’ by means of an only somewhat correct translation, I’d tend to the latter.

orionblastar 13y ago
Well I admit I don't understand it fully. That is no reason to accuse me of trolling or downvote my comments. http://en.wikipedia.org/wiki/Polynomial http://en.wikipedia.org/wiki/Polynomial Is Wikipedia not correct on this issue? I was told on one hand to look stuff up on Wikipedia, and on another I found out it is not always correct.
- claudius 13y ago
  ‘poly’ means many, yes, and ‘nomial’ in this context can stand for ‘terms’ or ‘expressions’ (not really numbers, but maybe formulae as you said). However, ‘polynomial’ does not mean ‘many terms’ when used by mathematicians and, in extension, computer scientists. A polynomial function, in this context, means a function that is/can be expressed as a sum of powers (usually restricted to a finite number of addends) of its input variables with appropriate prefactors. For example, f(x) = 1 is a polynomial function, but it certainly does not have many terms (nor numbers). That the finiteness of the sum is an important requirement when it comes to complexity can be seen by the fact that the exponential function can be expressed as an infinite polynomial: exp(x) = 1 + x + 1/2 x² + 1/6 x³ + … In other areas, where people are more concerned with nondivergent or differentiable functions, this requirement is often dropped and nearly everything that doesn’t have poles in x is called ‘polynomial’. Furthermore, you didn’t only get downvoted for misinterpreting polynomial, but also for the strange mixing of theoretical CS, which is concerned with the complexity of algorithms at hand, and real-world effects such as slowdowns due to other programs multitasking, CPU caches etc. etc. which are rarely taken into account when deciding whether a given algorithm is remotely feasible to implement (runs in time, say, n^10 or faster) or just too slow.
  - orionblastar 13y ago
    Ah I see, I am exploring theoretical areas of computer science for which there are no clear answers yet. Downvotes for you, bad HN user for making us try to think of new theories. :) So a Polynomial doesn't need be many of them, it can be just one of them. The poly in the name threw me off I admit. I would have assumed that was a mononomial for just one and two of them are a binomial but apparently polynomial is used instead even for only one or two? I hope you understand my confusion there. Thank you for clearing that up.
    - claudius 13y ago
      Just as poly- and mono- are prefixes of Greek origin[0], you’d probably use ‘di-’ rather than ‘bi-’ here (binomials are a little different, again), just as you have monosaccharides, disaccharides and polysaccharides[1] (aka carbohydrates). The relevant point is that it usually doesn’t matter whether you have one, five or 500 terms in a polynomial, as the largest one will certainly dominate for sufficiently large input sizes[2] and all terms in a polynomial essentially behave the same way (being differentiable, having no poles etc.). [0] The only thing wrong with homosexuality is smashing a Greek prefix onto a Latin root. [1] Latin: uno-, bi-, pauc-, multi-, Greek: mono-, di-, oligo-, poly- [2] cf. http://www.wolframalpha.com/input/?i=x%5E20%3B+x%5E20%2Bx%5E10+for+x+from+100+to+1000 http://www.wolframalpha.com/input/?i=x%5E20%3B+x%5E20%2Bx%5E...
    - nitrogen 13y ago
      Ah I see, I am exploring theoretical areas of computer science for which there are no clear answers yet. Downvotes for you, bad HN user for making us try to think of new theories. :) In science in general, including computer science, "theoretical" doesn't mean fringe or unexplored, it means foundational and abstract. CS theory uses the word "theory" in the same sense as music theory. CS theory deals with well-defined, rigorous analysis of computation in abstract or mathematical terms. I would have assumed that was a mononomial for just one and two of them are a binomial but apparently polynomial is used instead even for only one or two? A two-termed polynomial is also called a binomial. "Binomial" and "monomial" are special cases of the more general term "polynomial".

orionblastar 13y ago

Well I am trying to understand it better. Instead of explaining it to me better, I get downvoted instead. Please explain it further and tell me how you can estimate the time when a DDoS attack is being done on the system, or the CPU is overheating, I'd really like to know how you estimate that. Apparently I'm clueless and in need of many clues.

gurvinder 13y ago
With 25 years of experience in computer industry, you should be explaining us all how we can estimate the time when a DDoS attack is being done:). Anyways we are talking here about complexity of the algorithm, and not its actual speed or performance which will depend on a lot of factors. But complexity tells for example how many steps it will take for the algorithm to solve the problem. The algorithm can be used by Humans or super computers, so performance can vary from days to microseconds, but complexity will remain same.
- orionblastar 13y ago
  I think I covered that in this ebook: http://www.smashwords.com/books/view/314107 http://www.smashwords.com/books/view/314107 :) BTW it is a joke written by MIT's AI SciGen software to show how hard it is to tell if a thesis is serious or a parody written by clever AI software. Even if I mark it as parody and Computer Science Fiction some people are taking it seriously. Even when it says stuff like added 27 25Ghz Intel 386 chips to the network. :) The 386 chip does not run that fast. OK complexity, then why is polynomial time used to describe it? I know some compilers can optimize machine code better than others, how does that affect the complexity? If the performance can vary from days to microseconds, well that is a very big gap. Video gamers always complain about 'lag', and days well that is one heck of a 'lag'! :)
chc 13y ago
Your comment was not phrased along the lines of "Can anybody please explain this?" It was phrased as though meant to impart wisdom. That's why it got downvoted and why people are correcting you — because you (apparently) meant to ask a question but ended up making a bunch of erroneous claims instead.