bigocheatsheet's People
Forkers
agfor qpleple vault makosblade kylekolpek wbl yoavfrancis thomasahle bahadorsaket janodev jfriedly elefevre mufid wchen02 olifante r8-forks kittaaron veenviz ramakrishna-jujare sharpobject ben335 nojhan alex-ivanov criszhao bl323 efreykong cristaloleg caspervg pkwd nodirt michaelrbock carlosmarin jeremyjs steven41292 trevordavenport marfarma hipsterzipster rahulc93 forkingitup wanderingstar thefotios anshulk patelanuj28 justynazander mamigot zhangz mxj4 dennistt zdharmawan andyras tomjal zhixing drewhannay sandeshsingh gabeasley1 nishnet2002 nikhildhaka abhishekgahlot kennylv teodorrupi bsansouci bartmassey-upstream maraimelbadri danielma156 mhoffman fcfort kamyu104 joeferrucci dodgymike gibsjose phamtrisi sadineni63 marshallseid bbodenmiller ppaltmann martenc koek67 blog1729 pombreda pschiavone nnamso robbinespu pb1234 aureooms-contrib henry12116 alangeovs uxdxdev wizard-cxy aymanim yesyayen jayakumaur p3po alexhudici twistedmove mdaronco davidonlaptop maja-lin chothia adam-arold juanpantojabigocheatsheet's Issues
HTTPS support
Would be nice to have :)
Use GitHub Pages + CNAME
One suggestion is to use GitHub pages and just add a CNAME to your repository. If you create a branch called gh-pages, it will automatically update the website. This way you won't have to worry about keeping the server and code in sync.
Read more about GitHub Pages here.
Website doesn't load without www.
Trying to navigate to the site from google results in a server error. The site completely fails to load with bigocheatsheet.com
but works if you manually change the url to www.bigocheatsheet.com
.
Revert latest commit
@ericdrowell committed 1193ed2 13 months ago.
The changes in that commit are wrong. Theta and Omega do not mean average case and best case time complexity. Theta, Omega, and Big-O are completely orthogonal to the concepts of average-case, best-case, and worst-case. Strictly speaking, most of the time we say an algorithm is O(p) for some polynomial p, we really mean it is Θ(p). In any case, the information on this page is misleading, and my students now come into class believing that theta is equivalent to "average case," when this is plainly false, because they have heard that this page is the premier resource for algorithm time complexity.
Suggest reverting 1193ed2.
Add different graph algorithms
Kruskal, Dijktra, Prim, Hungarian and so on...
Singly Linked List O(1) deletion
I think it's misleading to say that it's O(1), since it assumes that you already have the element previous to the one to delete. It should also specify that there is a search time involved, either by specifying O(n) or as a tooltip. Also, in the wiki source, it is specified that there is a search time.
Misspelling of Cartesian
Cartresian -> Cartesian
Still being maintained?
Hey, I just wanted to check if this project is still being maintained? It seems like the site is used pretty heavily as a reference and thankfully a lot of these algorithms don't change over time (hehe...) in runtime complexity so more or less it's been great. The last commit in this repo has been a year ago so I'm hoping it isn't going to die off. At the very least, maybe there can be a handful of the contributors that would be willing to help maintain this site and they can be distinguished?
It also looks like a giant portion of runtimes was deleted by accident..? Not that I'm involved but I'm seeing a lot of redundant PRs adding the same run times so it would be good if these were either just merged or closed.
Thanks for your hard work on this project @ericdrowell! Let us know :)
Add amortized runtimes
Big-O notation can be helpful for lots of things, but amortized runtimes can be just as helpful as big-O time-complexities (sometimes moreso).
Including them in the tables would be incredible.
Add traversal complexity (previous, next element)
This is sometimes different from the access time.
Example:
https://en.wikipedia.org/wiki/AVL_tree#Traversal
Once a node has been found in an AVL tree, the next or previous node can be accessed in amortized constant time.
Multilingual Support
Last year, I forked and translated the entire html to brazilian portuguese, even the articles url. It would be very interesting if the official website had an option to choose the language, so that other contributors could translate to their mother languages and reach more people.
Omega And Theta
In some of these tables (e.g. array sorting), a 'best' and 'average' case are included along with the worst case, and they use the big O notation as well. Are the best case runtimes of these algorithms not Omega and Theta, respectively?
I'm in the process of beefing up my CS theory and there seems to be a ton of conflicting information in the community about asymptotic analysis and Big O notation. Not trying to nitpick on this (and my understanding of this could be off-base), but wouldn't the best case runtime for an algorithm be represented as Ω(n) and the average as ϴ(n), not O(n) since Big O implies the worst case?
Shell Sort: All complexities seem to be wrong
The time complexities for Shell Sort on bigocheatsheet.com are now nothing like the ones listed on the wikipedia page:
https://en.wikipedia.org/wiki/Shellsort
Incidentally, bigoref.com seems to have this mostly right, but not completely:
josem/bigoref#3
Any chance we could add stability to the charts?
In the sorting table, it would be relatively easy (and helpful) to indicate stabilities. If so I'd submit an initial pull request.
Add O(nlog^n) to Chart
Can we replace the existing image with the one below?
Shell sort has time complexity O((nlogn)^2)
in its average and worst case, but this function is not included in the chart provided.
Here's an iframe linked to an interactive version:
<iframe width="840" height="466" seamless frameborder="0" scrolling="no" src="https://docs.google.com/spreadsheets/d/1V6hJ9R0Tx9JMa0pEUq2TTkMFCkVO00vdusFFUYLmhbw/pubchart?oid=1753507166&format=interactive"></iframe>
Timsort wrong space complexity on poster
Timsort space complexity is indicated as O(1) in yellow on the poser, but must be O(n).
Worst case Singly-Linked List Insertion/deletion is O(1)
Shouldn't the worst case insertion/deletion time of a Singly-Linked List be O(n). Both would involve traversal of the entire linked list to find the last node.
Added Complexity Names with descriptions and examples
Isn't "Theta" is actually "Big Theta" ?
Add square root to the algo complexity image
Please add square root of x to the complexity /growth image
Worst-case space complexity of Quicksort should be set to O(n)
Right now, the worst-case space complexity for Quicksort
, is set to O(log(n))
. This is not right - the average-case space complexity is Θ(log(n))
, but when you attempt to sort an already sorted list, this will lead into n recursive calls on the stack, thus the O(n)
worst-case space complexity.
Should make the difference between comparison sorting and others
Comparing bucketsort to quicksort is like comparing apples and oranges. It is also important to understand that O(n log n) for comparison sorting is asymptotically optimal (up to a constant factor), and so it should not be ``Bad''.
Isn't insertion in a (unsorted) dynamic array O(1) instead of O(n)?
Recommend social image
I recommend the website add an Open Graph meta tag so that an image preview is added to link as it's shared.
Merge sort space complexity is O(n log n)
There are log2(n) levels of recursion and at each level n elements are used. that makes the total O(n log n) in space complexity.
Cracking the Coding Interview 6th Edition available
Could we update the recommended reading section to point to the 6th edition of cracking? Currently it points to the 5th edition
Link:
http://www.amazon.com/Cracking-Coding-Interview-6th-Programming/dp/0984782850/ref=sr_1_1
Qualitatively: O(2^n) vs O(n^2) are vastly different. (And other labeling issues.)
If you think about orders of magnitude of difference, I think the buckets ("Horrible", "Bad", "Fair", "Good", "Excellent") are done incorrectly.
O(2^n) and O(n^2) are vastly different, but both are labeled "Horrible." O(2^n) algorithms fall over long before n = 1000, O(n^2) algorithms can be practical and useful for n = 1 million.
O(n log(n)) and O(n) are not very different, but one is "Good" and the other "Fair". Both are practical for roughly the same class of problem. In many cases O(n log(n)) algorithms are preferred in practice over O(n) algorithms for non-complexity reasons, because the theoretical complexity difference is dominated by other factors.
O(log(n)) and O(1) are actually quite different, but both are labeled "Excellent." This is the least worrying of these, but if any factor of log(n) is important enough to distinguish labels, it's the first one. In this case, it's mostly because of CPU caches and memory accesses. Small constant memory access is relatively cheap, O(log(n)) memory accesses can have dramatic effects on cache misses and resulting performance of a whole program.
Added Complexity Names
Adding the whole page
Hi!
Would you mind adding all the code of the page? I'd like to try to integrate MathJax.
Please add me "Ray Pereda" to list of contributors on http://bigocheatsheet.com/
@ericdrowell
I made a contribution via this PR: #81
Please add me if you don't mine to the list of contributors.
BigOCheatSheet is a great idea, and glad to be a small part of it.
Ambiguity in Graph section
There is variety of ways to represent graphs, and complexity of graph operations depends on graph representation. However, I am curious how you estimated complexity of edge insertion, which is the same for all graph representations (add Edge, O(1)). What kind of graph implementation you assume hereby? Do you assume that you have a hash_map for vertices in adjacency list, which makes it O(1)? If so, it would be good to update the information.
To depict the issue, one can imagine very simple representation of a graph with vertices that contain strings. In c++ we can represent adjacency list using STL collections, such as:
std::mapstd::string,std::setstd::string adjacency_list;
Now, method to add edge, i.e. addEdge("baby","carrot"), first has to look up for position of the vertex ("baby") in the adjacency list, which is O(logn) in this case.
Color keys
Coloring is hard to define.
For eg, finding the shortest-path in a graph with negative edges:
- Dijkstra is fast, takes O((V+E) log V) but does work with negative edges.
- Bellman-Ford is O(VE), it's way slower than Dijkstra.
Would you put Bellman-Ford in green because it's the fastest you can do in that situation? Or in red because it's slower than Dijkstra?
How about absolute colors for each of the following categories?
- white: constant-time, O(1)
- blue: sub-linear, like O(log n) or O(sqrt n)
- green: linear, O(n)
- yellow: quasilinear, like O(n log n)
- red: higher, like O(n^2), O(n^2 log n), O(n^3)
I don't think you would ever want to list an exponential time algorithm, O(2^n), O(n!), O(n^n), so no color needed
Quicksort worst case runtime can be O(n log n)
In this issue, it was decided that quicksort worst case runtime is O(n^2)
based on a paper which contained an assumption that leads to unnecessarily slow quicksort implementations. In my opinion, the cheat sheet should contain the running time of the asymptotically fastest implementation of each algorithm, which runs in O(n log n)
in this case.
You are misunderstanding O vs. Theta.
You seem to be making the common mistake of thinking big-Theta means average case and big-O means worst case, which is not correct.
Either big-O or big-Theta or big-Omega can be used meaningfully to describe any of best, average, or worst case -- the concepts are completely orthogonal.
To be mathematically accurate your page should have Theta everywhere.
Poster product link leads to 404
The redbubble product link leads to "product not found" page.
fixed-size array is missing
There are cases where a fixed-size array is a good data structure. It has always O(1) for insertion, deletion and search Why is it not there yet?! :-)
PDF version
Since this is a cheatsheet I'd say it would be nice to also have it in a PDF form for offline/print use.
What do you think?
add: pre-knowledge about big o notation & translations section
I already provide a PR here #153
Might as well review it immediately
Thank you 🙏 @ericdrowell
Add visual asymptotic notations
Associative Array
I thought that the data structures section should have a more general link to an associative array/map/dictionary. I see a link exists for a hash table which is just an implementation of an associative array.
Sorely Missing Binary Search on an Array
http://en.wikipedia.org/wiki/Binary_search_algorithm
Probably the only thing else it needs.
How about B+ Tree ?
Should most entries have no Theta() time complexity set listed?
- In set terms Theta() is the intersection of O() and Omega() [more info at the highest ranked answer in this complexity question on stackoverflow].
- Very few algorithms have Theta() (merge sort being one of the few examples), however all algorithms in the cheatsheet seem to have entries).
- There also seems to be mixing between best, average, worst and the mathematical concepts of big Omega, Theta, O.
Add section headers to nav bar
Currently, the nav bar has
Searching
Sorting
Graph
Comments
It's missing Data Structures and there's a bit of name collision between graph algorithms and the Big-O complexity graph.
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.