Recently, I have seen in many papers reviewers are asking to provide computation complexities for the proposed algorithms. I was wondering what would be the formal way to do that, especially for the short papers where pages are limited. Please share your expertise regarding the computational complexities of algorithms in short papers.
Thanks in advance.
In my personal experience, providing the pseudocode followed by a short paragraph explaining the procedure and the complexity would suffice. However, for certain fields, especially novel methods, much more through theoretical analysis might be needed. It might be best to check relevant papers to see how other field experts handle this issue. And definitely, take a look at recent publications of the journal you are submitting to as well.
Hi Sina Abdipoor ,
Thanks for your reply. Can you share some references for the short paper (e.g., letter)? It would be more helpful to understand.
Dear Anik Islam Abhi
In simple words, Computational complexity is an assessment of how much computer resources (time and space) a specific algorithm uses while it executes.
Kind Regards
Qamar Ul Islam
Dear Anik Islam Abhi
Zhang, M. X., Zhang, B., & Qian, N. (2017). University course timetabling using a new ecogeography-based optimization algorithm. Natural Computing, 16(1), 61-74.
Refer to section 5.2
You can assume each operation that your algorithim need it. Then, you can calculate the sumuation of an assumed operations
You can see my paper in an attaxhments
https://www.researchgate.net/publication/351691395_An_Efficient_Mechanism_to_Prevent_the_Phishing_Attacks
formal way to do the algorithm strategies you should try the particular theorem of certain problem and proposed them into the system.
In my opinion ... all the computational complexity analysis methods are not really fundamental. There are two fundamental kinds of entropy in Physics (the others are wild hypotheses, IMHO) they are (1) QM Entropy, which would be hard to apply here and (2) statistical entropy from Boltzmann, which I think is easier. They are both real and fundamental.
Entropy is what happens when you put energy into an engine and get less than that energy output as work. The difference is entropy, as heat which disorders the engine and causes damage. As your engine gets older, it does not produce as much work, but a lot more heat and smoke until it dies. Kind of like humans, and other living things. Simply, huh? Here's the math: https://en.wikipedia.org/wiki/Entropy#Statistical_mechanics
Look at the simple fourth equation S = kb log Omega. So entropy is related to the log of the number of micro-states of the system. Think of this simply, a gas engine has more moving parts (macro-states to heat up into micro-states and break down) than a diesel engine, which has more than a Wankel engine, and the simplest is an electric motor. Of course anything can be badly designed and have defects which break down quickly, but building in more entropy does not change the equation.
So, in software, entropy arises from too many threads, too much working set flowing through the system, causing too much queuing, which everyone knows is the weakest and least tested kind of code, and when something untoward happens in the system (guaranteed by things like Kolmogorov's Law) buildup of stuff creates more opportunities for data races, etc. Boom!
It's kind of like having more virus mutating out there in the wild, something bad will evolve quicker. That might be an example of Boltzmann's Law as well, not sure.
Entropy is what happens when you put energy into an engine and get less than that energy output as work. The difference is entropy, as heat which disorders the engine and causes damage. As your engine gets older, it does not produce as much work, but a lot more heat and smoke until it dies. Kind of like humans, and other living things. Simply, huh? Here's the math: https://en.wikipedia.org/wiki/Entropy#Statistical_mechanics
Thanks everyone for your valuable opinions. I have summarised all and applied it in my letter (i.e., short paper). It got accepted and published in IEEE Wireless Communications Letters. Please feel free to check it.
Article FBI: A Federated Learning-Based Blockchain-Embedded Data Acc...
These sources are very helpful:
Cormen: Introduction to algorithms.
S. Cook: P and NP theorem.
Please remember about last publication that P and NP equality still not proved, so that your algorithm goes beyond polynomial one.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Artificial Intelligence