4 ms·

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

It is designed to estimate the amount of time it takes to run an algorithm using a data structure like a binary tree instead of a different one like a linked list O(n)instead for linked lists. I am trying to learn it myself, so bare with me if I make any mistakes. They throw words like polynomial and I've asked people with comp sci degrees to define what they are. I get back replies like "We learned it as a polynomial and never got a definition of it." OK look, here is what it means and some people with a comp sci PHD cannot even tell me, poly means many, right, and nomial like numbers or formulas or rather in computer science and algorythm. You have to study how algorithms work, I asked this on Hacker News and many tried to bury the story because most couldn't even answer that, and thanks to those who did. I am glad to see someone else bring it up and hope it sheds more light on it. Consider this, that you really cannot get a good estimate of how long any algorithm can run because you got other factors in play. You got multicore CPUs now, and some of the work is offloaded to GPUs as well (like Bitcoin mining programs using GPUs, well now algorithms can use GPUs for some of the processing), plus you got caches on processors you didn't have in 1971, not only that but the law of thermodynamics applies to computers and electronics and many people forget that, so if your CPU is over heating it could slow down if you have a variable fan it could cool the CPU down and it runs faster for a bit and then heats up and slows down a bit, most operating systems are multitasking so the program that runs the algorithm might take longer if the Apache HTTPD server is in use with heavy traffic on the server the algorythm runs on, not only that but Anonymous might have sent a DDoS attack to your server the algorithm is running on. I hope those with a PHD in computer science figure those as factors when they explore this issue.

tincholio 13y ago
>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.
      - 13y ago

tincholio 13y ago

>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.
    - 13y ago