views:

554

answers:

4

If I have an algorithm that takes n log n steps (e.g. heapsort), where the steps take log n time (e.g. comparison/exchange of "big" integers in the range 0 to n-1), what is the asymptotic bound for the whole process.

Obviously we can say "n (log n) (log n)", but I'm having a hard time trying to convince myself that I cannot simplify this to "n log n". At the same time, I'm having a hard time justifying the instinct that insists that I can.

Is my instinct just plain wrong on this?

EDIT

It seems my simple-example-to-avoid-complicating-the-issue has complicated the issue. Oh well.

The real reason for the question is that I often have a standard algorithm with a known complexity, but implemented using different underlying containers, so that the individual steps are O(log n) rather than O(1). For example, Hopcrofts automaton minimisation algorithm is O(n log n) - but if you start using binary tree containers for the states, transitions and intermediate results, the steps themselves become O(log n) - the O(n log n) is no longer valid because the assumption of O(1) accesses is invalid.

Still, people will claim that there are n states and m transitions, but n and m tend to be linearly related for automata, assuming that the number of transition annotations is constant and that the automata are more-or-less deterministic.

I haven't worried too much about this in the past - the cases I work with aren't very big. But, well, I'm doing a major refactoring of my automata code, and I thought I might as well do the math properly for some key algorithms as I go.

EDIT

I'm also increasingly convinced that the "n (log n) (log n)" is wrong.

If a is O(b log b) where b is O(log c), what is a in terms of c?

+2  A: 

You won't be able to reduce n (log n) (log n) to n (log n) simply because that's not a reduction by a constant factor.

What's wrong with n (log n)2?

paxdiablo
+5  A: 

In general, you can't multiply complexities like this: for heap sort, N indicates the number of items in the heap, whereas for the big integers, N probably indicates the upper bound of possible values. In general, these don't have to be related, so that it's rather N log N log M (where M is the range that the items may take).

In a specific application, most likely, the large integers follow some specific distribution. For example, it may be known that they are all below 10^20. If so, the comparison operations take constant time (determined by an upper bound of 10^20). Then, log M is also constant, and the entire complexity is in O(N log N).

Martin v. Löwis
That's a point I didn't pick up on - big-O tends to have one input variable and OP is using two disparate ones. +1 and comm-wiki'ing my answer (it's still useful in the case where the big-O is actually n.log(n).log(n), but not in this case).
paxdiablo
Please see edit above
Steve314
The edit doesn't make sense, mathematically: O(f) is a set; namely a set of all functions bound by f. So you can't really nest the O applications.
Martin v. Löwis
@Martin - Are you claiming that it's invalid to compose a complex algorithm from simpler ones, and then reason about the complexity? When I swap out a building block, replacing constant-time steps with O(log n) algorithm calls, that's really all I'm doing - and it's hardly original. There's textbook cases where a binary heap is swapped out for a fibonacci heap in a larger algorithm, such as Dijkstra. The steps are non-constant-time heap operations. In the fibonacci heap, it's even the amortized complexity of steps that's important. "Nesting" the O seems uncontrovertial - until I do it.
Steve314
You can certainly analyse the complexity of a complex algorithm by analysing the complexity of the subalgorithms. However, a) you need to keep track what the problem size is; in your example, the subalgorithm has a parameter completely independent of the parameter for the whole algorithm, and b) you can, at best, combine the functions *inside* the O(f) notation (i.e. the fs), not the Os.
Martin v. Löwis
All I wanted was to check how log-based functions work WRT nested algorithms. I wanted to check a BASIC PRINCIPLE, NOT to get others to do the work for me. a) *BY* *DEFINITION* those parameters are *NOT* independent, because that is what the whole point of the question - of the principle I was trying to check. Sorry if that wasn't understood when I first asked. b) I'm very very sorry for my imperfect terminology. I thought trying to explaining what I need to know was enough - I didn't mean to upset you. c) you got my upvote already - it's a good point WRT the question I didn't mean to ask.
Steve314
No need to apologize :-) If the parameters are not independent, you still need to define the precise dependency (or an upper bound for it) to get useful results. For example, in a graph, if you have N nodes and E edges, in general, E may be as as N^2. So if you have an algorithm that is O(N*E), this means O(N^3). However, if you know that your nodes have a fixed degree, then E is in O(N), and the entire algorithm in O(N^2).
Martin v. Löwis
+3  A: 

Here's a proof by contradiction:

Let's say that a function f(n) = n(log n)(log n). Assume that we think it's also theta(n log n), so in other words there is an a for which f(n) <= a * n log n holds for large n.

Now consider f(2^(a+1)):

f(2^(a+1)) = 2^(a+1) * log(2^(a+1)) * log(2^(a+1)) = 2^(a+1) * log(2^(a+1)) * (a+1), which is clearly larger than a * 2^(a+1) * log(2^(a+1)), and we have a contradiction. therefore f(n) is not an n log n function.

Yuliy
I'm accepting this as answering the question I asked, but every answer has helped - even the one I disagree with.
Steve314
+1  A: 

Okay, the general complexity measure of a program is the following:

Complexity O(f(n)) means, that there exists c, such that the number of the corresponding Turing machine steps before it terminates is not more than c*f(n), where n is the length of input.

In this definition everything is taken into account, because the integer numbers may be arbitrarily big, and arithmetic operations on them would also increase the function under O(n).

But if we were programming Turing machines directly, your question wouldn't have been arisen. In real world we prefer to abstract. While we still calculate "steps" that are needed to run the program, we assume that certain operations take one step. We assume that by different reasons:

  • It may resemble the actual work of the CPU, where each 32-bit integer addition is indeed one step (and there exist algorithms that actually abuse it, e.g. "bit-verctor dominators").
  • We compare different algorithms in same domain (for example, comparing array sortings by measuring the number of comparisons).

In this case (your first EDIT), if you want to concretize your complexity measure, you should just multiply functions under O. If what you thought to take one step now considered to take O(log N) steps, then the amount of concretized steps increases by a factor of O(log N). Therefore the total complexity is O(N*log N*log N).


As to your second EDIT, it's a different situation. Let your algorithm be a complexity of O(n*log N). But you know that the input consists of M numbers, each of log K digits, so `N = O(M*log K) (we need to account separators, etc). It's mathematically correct then to write the overall complexity as O(M * log K * (log M + log log K)), so there's no problem here. But usually we abstract away unnecessary details to find a common basis for different algorithms to be compared.

Pavel Shved
So - given that the real problem (first edit) is a theoretically O(n log n) algorithm, but using the wrong underlying containers such that individual steps take O(log n) time - the container size being linearly related to the size of the original problem - the result I'm looking for has M and K linearly related giving O(n (log n)^2 (log log n)).
Steve314
@Steve314 , no that wasn't what I was talking about. I fixed my post to clarify it.
Pavel Shved
Never mind. I have clarified the basic principle I needed to know. On giving some though to what you say, I realise I'm carrying around some extra assumptions that I haven't specified - I know how I am implementing Hopcrofts algorithm, so I know more about those (n log n) steps than the (n log n) summary explicitly states). The whole point is to compare the effect of my switching out the underlying containers - to find how my implementation compares with the unmodified Hopcrofts algorithm (badly, but how badly?), so now it's time to do the math.
Steve314