Hacker News Reader

Comment by mcantor | Hacker News Reader

Sorry, I should have been more specific: I understand the rules of Big O complexity, which you aptly summarized; the part I'm really curious about is "From there, you can pretty much combine these rules to analyze many algorithms." It's not that the concepts are mysterious to me, but that making them a part of my learning habits has not come naturally.

View on HN

> the part I'm really curious about is "From there, you can pretty much combine these rules to analyze many algorithms."

I'm not sure if I'm still misunderstanding you, but here's an example of what I meant.

Say, for whatever reason, you want to populate a binary tree with k items of random data:

    for(int i = 0; i < k; ++i) {
        int data = rand(); // Let's assume this is O(1)
        tree.insert(data); // O(log(n))
    }

The inside of the loop runs in O(log(n)) time because O(log(n)) > O(1). We're doing it k times, so the total time is O(klog(n))
Now, if you wanted to do this for m trees:
for(int j = 0; j < m; ++j) { for(int i = 0; i < k; ++i) { int data = rand(); tree[j].insert(data); } }
We already know that the inner loop runs in O(klog(n)). Since we've just added a loop around that, it's easy to see that the whole thing runs in O(mklog(n)) time.

We already know that the inner loop runs in O(klog(n)). Since we've just added a loop around that, it's easy to see that the whole thing runs in O(mklog(n)) time.

This is not necessarily true for all cases. (It is for yours.) It's possible for interaction to exist between a loop and its contents, such that the total time is not m times the running time of the interior of the loop.

  for (int i = 0; i < data.length(); i++)
      bubble_sort(data);

That's a trivial case but sufficient to prove the point. Bubble sort runs in O(n^2), and it looks like we're doing that n times, so the whole thing runs in O(n^3). But that's not true, since bubble sort runs in O(n) when the array is already sorted, so the whole thing is still O(n^2). In other words, the first iteration of the loop induces a side effect that affects all later iterations.

That is true, but one generally doesn't care about the best case. It's a good point though.

(Also, if data is a linked-list, length() could be an O(n) operation. That would make this O(n^3) or O(n^4) ;))

Reply on news.ycombinator.com