How to calculate big-theta
Can some one provide me a real time example for how to calculate big theta. Is big theta some thing like average case, (min-max)/2? I mean (minimum time – big O)/2 Please correct me if I am wrong, thanks
complexity-theory
Exactly how many comparisons does merge sort make?
Let’s see if we can work this out! In merge sort, at each level of the recursion, we do the following: Split the array in half. Recursively sort each half. Use the merge algorithm to combine the two halves together. So how many comparisons are done at each step? Well, the divide step doesn’t make … Read more
Is log(n!) = Θ(n·log(n))?
Remember that You can get the upper bound by And you can get the lower bound by doing a similar thing after throwing away the first half of the sum:
Big-oh vs big-theta
Big-O is an upper bound. Big-Theta is a tight bound, i.e. upper and lower bound. When people only worry about what’s the worst that can happen, big-O is sufficient; i.e. it says that “it can’t get much worse than this”. The tighter the bound the better, of course, but a tight bound isn’t always easy … Read more
What is O(1) space complexity?
To answer your question, if you have a traversal algorithm for traversing the list which allocate a single pointer to do so, the traversal algorithms is considered to be of O(1) space complexity. Additionally, let’s say that traversal algorithm needs not 1 but 1000 pointers, the space complexity is still considered to be O(1). However, … Read more
What are the differences between NP, NP-Complete and NP-Hard?
I assume that you are looking for intuitive definitions, since the technical definitions require quite some time to understand. First of all, let’s remember a preliminary needed concept to understand those definitions. Decision problem: A problem with a yes or no answer. Now, let us define those complexity classes. P P is a complexity class that represents the set of … Read more
HashMap get/put complexity
It depends on many things. It’s usually O(1), with a decent hash which itself is constant time… but you could have a hash which takes a long time to compute, and if there are multiple items in the hash map which return the same hash code, get will have to iterate over them calling equals on each of them to find a match. … Read more
Big O, how do you calculate/approximate it?
I’ll do my best to explain it here on simple terms, but be warned that this topic takes my students a couple of months to finally grasp. You can find more information on the Chapter 2 of the Data Structures and Algorithms in Java book. There is no mechanical procedure that can be used to get the BigOh. As … Read more
When will the worst case of Merge Sort occur?
The worst case of merge sort will be the one where merge sort will have to do maximum number of comparisons. So I will try building the worst case in bottom up manner: Suppose the array in final step after sorting is {0,1,2,3,4,5,6,7} For worst case the array before this step must be {0,2,4,6,1,3,5,7} because here left subarray={0,2,4,6} and right … Read more
Example of O(n!)?
There you go. This is probably the most trivial example of a function that runs in O(n!) time (where n is the argument to the function):