What time complexity (big o) is this specific web crawler implementation?

Question

Note: this question was marked as a duplicate in favor of this question/answer which attempts to provide a generic formula for translating code to mathematics.

Unfortunately I didn't find that response useful as I don't have a good understanding of maths and so all I see is complex symbols that don't mean anything to me. I require a more lay person explanation of how to break down an algorithm into time complexity.

I've built a simple 'web crawler' and was interested to know what the time complexity of the core 'processing' logic was.

Here is a diagram of the architecture:

https://github.com/integralist/go-web-crawler

Specifically the algorithm portion I'm interested in is the Crawler which:

1. defines a worker pool size
2. pushes tasks into a channel
3. processes tasks concurrently within the boundary of the pool

In the crawler code we:

• accept a list of n items
• each item in the list has a nested list of x items
• we look at each item and decide whether to process the item or not

Note the Parser and Mapper portions of the code are all the same underlying design, but how the 'task' is processed is slightly different and so although I could imagine the time complexity for those possibly being different depending on what those processing steps are, the principle is still the same: we're still looping over all items and deciding on something to do.

What is this BigO time complexity?

Initially it might seem that this is just O(n) as we're visiting each item in the list as well as each item in the nested list.

Is that it? or am I missing something else entirely obvious.

I don't think it's O(n Log n) as it's not reducing the number of looping operations in the nested lists. Similarly for O(n*n) as the nested loop isn't necessarily the same length as the parent list. I also don't think it's O(2^n) as the nested lists aren't growing exponentially (they're just an unknown number of items).

---

Update

I was asked to provide a precise definition of the algorithm, and so I'll attempt to do that below by way of a bullet list along with some pseudo code...

• loop over collection (collection: array of structs)
  • pass each struct within the collection to crawl function

breakdown of crawl function...

• get length of collectionItem Urls (collectionItem: struct with field containing urls)
• create worker pool of set size, or size of collectionItem.Urls (if smaller)
• each worker stays open (blocked) waiting for a task to process
• when a task is received:
  • make a http network request (task is a url)
  • track the task (a url) in a hash table
  • append network response in an array
• loop over collectionItem.Urls
  • if url already tracked in hash table:
    • do nothing
  • else:
    • push url into task queue

for item in collection {
    crawl(item)
}

func crawl(collectionItem) {
    collectionLength = length(collectionItem.Urls)

    if (collectionLength < 1) {
        return
    }

    poolSize = 20

    if (collectionLength < poolSize) {
        poolSize = collectionLength
    }

    for i=0; i<poolSize; i++ {
        // we spin up multiple threads...
        waitForATask(
            // this function is executed concurrently on individual thread/process
            // it contains the following logic...

            for t in tasks {
                // tasks is a blocking channel
                // so as tasks are pushed in the channel
                // it means the tasks are distributed across the pool

                page = netRequestFor(t)
                trackInHashTable(t)
                appendToArray(page) // this is ultimately what process returns
            }
        )
    }

    for url in collectionItem.Urls {
        if not trackedAlready(url) {
            pushTaskIntoQueue(url) // queue is the 'tasks' variable we loop over within our threads
        }
    }
}

Additionally! the steps described above (i.e. looping a collection, and then passing each item to a crawl function) is something that will be recursively executed. The actual implementation is...

func process(mappedPages []mapper.Page) {
    for _, page := range mappedPages {
        crawledPages := crawler.Crawl(page) // this is what I described above
        tokenizedNestedPages := parser.ParseCollection(crawledPages)
        mappedNestedPages := mapper.MapCollection(tokenizedNestedPages)

        for _, mnp := range mappedNestedPages {
            results = append(results, mnp)
        }

        process(mappedNestedPages)
    }
}

...The idea being that the top level loop will not only pass each item to the crawl function, but that the results (a list of requested pages) will itself then be passed to a parser function (tokenizing the page, and which is designed with an algorithm exactly the same as the crawl function), then that tokenization result is passed to a mapper (again, the mapper is designed the same as the crawl).

So I guess when considering the time complexity, we would need to take into account the whole algorithm (not just the crawl function segment).

Answer 1

I didn't read your code, but based on the overview, the running time to handle a list of size $n$ containing nested sublists of size $x$ appears to be $O(nx)$. Here's my reasoning:

• You iterate over each list (there are $n$ of them), and each contains $x$ items, so you iterate over $nx$ items in all.

• The amount of work per item appears to be constant, i.e., $O(1)$ (it doesn't appear to depend on $n$ or $x$; here I'm using that the running time for insert or lookup operations in a hashtable are $O(1)$, in practice).

• Multiplying those together, we see that the total time to handle that list is $O(nx)$.

That said, beware that big-O analysis is of dubious utility for systems code like yours. I'm pretty skeptical whether this is useful at all. Big-O analysis ignores the constant factors, but for systems code, we often care about the constant factors a lot.

And these constant factors can be enormous. Big-O analysis treats executing a single ADD instruction the same as fetching a web page at some URL; they both take $O(1)$ time. However, in practice, the latter takes are longer: a single instruction might take 1ns, and fetching a URL might take 100ms. That's a difference of $100,000,000\times$, i.e., 8 orders of magnitude. Counting both operations equally, as big-O analysis does, is simply not helpful for understanding the performance of the system in practice.

So, I would exercise caution in your use of big-O analysis (i.e., asymptotic running time) in systems like these.