gnansu (4) [Avatar] Offline
#1
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.
aditya.bhargava (59) [Avatar] Offline
#2
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!) ?
gnansu (4) [Avatar] Offline
#3
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 smilie

Thank you!
108594 (4) [Avatar] Offline
#4
I don't understand where the O(n!) and the term "Exact Algorithm" came from(Column labels). Any clarity would be greatly appreciated.

Thanks
Magnum (3) [Avatar] Offline
#5
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.
Magnum (3) [Avatar] Offline
#6
@aditya.bhargava:

1. In the radio stations problem (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. Thank you!

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)