3 ms·

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 ther

by mcantor 15y ago

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.

rcfox 15y ago
> 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.
- T-hawk 15y ago
  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.
  - rcfox 15y ago
    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) ;))

by mcantor 15y ago

rcfox 15y ago

> 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.

T-hawk 15y ago
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.
- rcfox 15y ago
  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) ;))