For the radio station problem, to calculate every possible set of substations, it takes O(n!). But I'm seeing the values in the 9.17 table is computed based on O(2^n).

For e.g. 5 stations, 2^5 = 32 subsets. So it takes 10 subsets per second, it is 3.2 sec

But should it be, 5! = 120 subsets. So time taken for 5 stations = 12 sec

Similarly for the other cases in the table

Correct me if my understanding is wrong.

The set of all possible sets of radio stations would be the power set. A power set has O(2^n) items, so it would take at least that long to calculate. Why do you say O(n!) ?

I think I misread or misunderstood the statement above the figure. It says, it takes O(n!) time to calculate all possible subsets. I was somehow thinking if there are n items, then there are n! subsets.

It would be helpful if you can mention about powerset and O(2^n) in the explanation

Thank you!

I don't understand where the O(n!) and the term "Exact Algorithm" came from(Column labels). Any clarity would be greatly appreciated.

Thanks

I believe it says "Exact" because that's the time it takes if ALL the cases/possible combinations where checked. We're trying to avoid such an "Exact" algorithm and instead come up with an "Approximation Algorithm".

In this chapter of Greedy Algorithms, the idea is to make an "approximation algorithm" so that it doesn't take O(n!), but instead a lower time.

@aditya.bhargava: Thank you for your amazing book. Could you help us with this?

1. In the radio stations problem time table (Page 152). I'm confused, similar to OP and the user above me, as to why use O(2^n) and not n! to calculate the Exact Algorithm's time. As shown in Table Page 152. Thank you!

UPDATE: I believe the Big O should be 2^n as explained in page 165. Please correct me if I'm wrong

For anyone interested. For "Set-Covering" problems, the Set containing all possible subsets/permutations (including the empty set and the whole Set itself) is called the Power Set as the books says.
Now, the number of all possible subset is calculated using 2^n where n is the number of elements in the Set.
At first, I didn't get that this is a given formula you have to trust, mathematicians came up with this.

In this case, n is the number or Radio Stations. Eg. For 3 Radio Stations, there are 8 subsets (or 8 different arrangements of the Radio Stations).

Take a look at Power Set(wikipedia). In the "Example" section, the exercise of a Set with 3 elements {x, y, z} = 8 subsets.

For many other NP-Complete problems, the Big O is O(n!) or factorial, as explained in the traveling-salesperson problem in page 157.
See attached image for a proposed fix in the table 9.17.






UPDATE: YOU COULD IGNORE THIS QUESTION.
2. Is "Simple Search" a Greedy Algorithm?
I say that because it has to check ALL possible solutions... same as with Breadth-First Search.
What makes me doubt if it is Greedy is that Simple Search is O(n) which is kind of fast... or at least it is not as slow as O(n log n) or O (n^2)[

UPDATE FOR ANYONE INTERESTED:
I thought Simple Search was a Greedy Algorithm bc it had to check all possible solutions. But actually, a Greedy Algorithm is one that "approximates the answer" (which could be wrong or not the best), and not one that checks EVERY possible solution.
Simple Search checks all the solutions, but IT IS NOT APPROXIMATING THE ANSWER. It always gets the correct answer.

Another thought: BFS and Dijkstra are Greedy. Why? could it be because they get a Local Optimal to reach a Global Optimal. Thereby, shortening the steps needed to reach a solution. BEAR IN MIND that these 2 algorithms, they get the CORRECT ANSWER, THEY DON'T GET AN APPROXIMATION OF THE ANSWER LIKE OTHER GREEDY ALGORITHMS.

Here's a slightly different definition of "Greedy Algorithm" that involves no-backtracking:

In simple words, an algorithm is normally considered "greedy" if

1. it builds solutions step by step without backtracking
2. in each step it picks what's best in the current state.

Source: Stack Exchange
http://cs.stackexchange.com/questions/44710/please-explain-a-greedy-algorithm-in-a-naive-manner/44742#44742

Last Edit: Mar 29, 2017 @ 10:43 PM
Last Edit: April 11, 2017 - Added definition Stack Exchange's definition of Greedy Algorithm.

* Updated and answered my question above *

I think the "Exact Algorithm" is a O(2^N), O(!N) is probably a typo. The O(2^N) runtime of the "Exact Algorithm" is already mentioned in Page 147.