## Drop algorithm 's complexity

### Drop algorithm 's complexity

Drop algorithm:

Given T terminals and C concentrators and a center.  Concentrators are
connected directly to the center.

Step 1: Assign all terminals to the nearest concentor's site,e.g.,
connect terminal j to concentrator i will cost less than connecting
terminal j to other concentrators. Then connect terminal j to
concentrator i.

Step 2: For every concentrator j, we need to see that if we move the
concentrator away and connect the terminals to the center will save
some money. If that is the case, just move the concentrator away and
connect the terminals to the center.

The answer is TC^3.

### Drop algorithm 's complexity

> Drop algorithm:

> Given T terminals and C concentrators and a center.  Concentrators are
> connected directly to the center.

> Step 1: Assign all terminals to the nearest concentor's site,e.g.,
> connect terminal j to concentrator i will cost less than connecting
> terminal j to other concentrators. Then connect terminal j to
> concentrator i.

> Step 2: For every concentrator j, we need to see that if we move the
> concentrator away and connect the terminals to the center will save
> some money. If that is the case, just move the concentrator away and
> connect the terminals to the center.

> The answer is TC^3.

You haven't provided enough information about the "cost less" and
"save some money" relations for anyone else to verify an O(TC^3)
complexity.  If connection cost is proportional to distance and
concentrators are free and their locations are given, the complexity
is O(TC logC).  If you are trying to find optimal concentrator
locations to get a Steiner tree, that problem is NP-complete but
heuristics based on Prim or Kruskal have polynomial time.
-jiw

Hey all,

I've encountered a problem lately I just can't find a good solution to: How
to calculate complexity of an image? A simple solution is to find the
standard-deviation for every channel, and it's generally an okay solution,
but what if I have an image that 90% percents of it are solid, and the other
10% are noise. Standard deviation 'swallows' such cases. On the other hand,
the data I'm dealing with is not perfect imagery, there are some 'glitches'
(although very small - 1-2 pixel(s) ) - I want such occurrences to be
avoided.

What methods can you recommend? What should I be looking for?

Help much appreciated,
Ofer.