Question:
Can someone explain time complexities, run time complexity, or Big-O notation?
?
2010-01-19 16:36:28 UTC
I don't understand Big-O notation, which is probably why I don't understand either run time complexity or time complexity. I know the formula, but somehow that's not helping me very much and even reading my math book and asking around campus hasn't been helping me. So I turn to you, internet-- can anyone help me understand Big-O and time complexity on a basic level?
Three answers:
Mantis
2010-01-19 16:57:52 UTC
Big-O is a way of describing how long (in terms of steps, not time) an algorithm will take and how that behavior changes as the size changes.



Don't think of it as anything all that precise. Think of it as a formalized rule of thumb. It's an effective way of comparing two different algorithms, and not much more than that.



Let me give you a standard but simplistic example. If you have an unsorted array of 10,000 elements and have to search them for a specific item, how many items do you have to look at? Don't think about big-o notation yet. Just think about how many elements you'll have to search. Don't let big-o get in the way. The answer is, you have to keep going until you find it. You start at the beginning and go until you get there. Nobody knows how long that will take because nobody knows where you'll find what you want. It could be the first item, it could be the last. If you have n items, you may have to search n elements to find it. O(n).



Consider if you had a sorted array of 10,000 elements instead. Using a binary search, you can start in the middle. If what you find is larger than what you want, you go half way between there and the first element. You keep doing this until you find where you are going. How many times will you have to do this? Nobody knows... it could be the very first search, it could the last. But it will be far, far fewer steps than would be required for the unsorted example. The worst case (and just take my word for this unless you're better at math than I am) would be log 10,000 searches. O(log n).



The big-O notation is there to help compare these algorithms. They aren't exact and may not have any relationship at all time actual time. It's more about the shape of how long something takes than a value. For example, the first search where you have to search all 10,000 elements (at worst) to find your answer is usually slower than a binary search... but under some circumstances it can be faster (like with a linked list, or a very short array).



So that's what Big-O is. Just an approximation of how many steps will be required to finish an algorithm. The first example was O(n), so if you have n items (10,000 for example) it'll take n steps to finish. The binary search is O(log n), so if you have n items it'll take log n steps at worst to find the item. It's just how many steps it takes, not how much time any given step takes.



Searching for a duplicate the easy way, which is to compare every item in the array to every other item in the array, will take O(n^2) steps. If you have 10 items that's 10 * 10 comparisons. 100 items is 100 * 100 comparisons. You can see that this is very expensive if you have millions of entries--but it doesn't say how long this is likely to take. Just that it will take longer and longer exponentially as the size increases. If you have might have a very large list you may want a different algorithm.



I hope this gives you the background you need to re-tackle the textbook. There are lots of resources on the web that list the big-O notation for various algorithms, but it all boils down to approximate size of an algorithm, and how the time required increases as the number of elements increases.



Good luck.
nevitt
2016-12-15 09:35:59 UTC
Explain Big O Notation
?
2016-02-26 07:47:54 UTC
This is a measure of how much work an algorithm does, compared to its input size. So, for example, a linear search will *on average* grow in time as fast as the number of items to be searched, and be O(n) ... if you have an efficient search system, say a well-balanced tree, the search tile could be less, say O(log n). Sorts usually require more work, and could be, say, O(n^2).


This content was originally posted on Y! Answers, a Q&A website that shut down in 2021.
Continue reading on narkive:
Loading...