Hacker News Reader

Comment by rcfox | Hacker News Reader

There aren't too many things to remember in order to be useful:

- Operations that take the same amount of time regardless of the input are O(1). ie: 1+1 takes just as long as 10000+10000 (okay, not really, but it's a reasonable assumption.)

- Doing a small sequence of operations runs in O(maximum of all operations). Doing 5 adds (which are O(1)) runs in O(1). Doing an O(n) operation followed by an O(k) (where k > n) runs in O(k) time.

- Looping n times over O(k) operations runs in O(n*k) time. (Assume n is fairly big.)

- Due to the structure of a tree, accessing a node is generally O(depth of the node). Max depth = log_m(number of nodes) for a full tree. (Where m is the number of children each node has. For a binary tree, m=2)

- From there, you can pretty much combine these rules to analyze many algorithms. These aren't by any means all of the rules, but they are some of the most useful in my experience.

View on HN

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.

> 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) ;))

1+1 does really take the same amount of time as 10000+10000 on nearly all CPUs.

Reply on news.ycombinator.com