0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I've updated this post in two ways: 1. to explain why the suggested question/answer isn't useful to me. 2. to give @DavidRicherby a better breakdown of the algorithm used. $\endgroup$ – Integralist Feb 23 at 8:46
  • $\begingroup$ It sounds like you are saying that you don't understand the basic concepts of running time analysis, so you're hoping we will apply them for you to your specific situation. However, your specific situation is detailed and complicated enough that I think that a better solution would be for you to learn the concepts of running time analysis, and then apply it to your own situation. Those concepts and techniques are described in standard data structures and algorithms textbooks. $\endgroup$ – D.W. Feb 23 at 21:51
  • $\begingroup$ It looks to me like your question contradicts itself. In one place, you say there is a list of N items, where each item has a nested list of N elements. In another place, you say "the nested loop isn't necessarily the same length as the parent list". I don't know how to resolve that contradiction; if the nested list and the parent list are both length N, then they have the same length. Also, you haven't told us what $n$ is. You use N in one place and n in another place. If you intend those to represent the same thing, you should use the same variable for both consistently. $\endgroup$ – D.W. Feb 23 at 21:53
  • $\begingroup$ @D.W. thanks for the feedback. I replaced N with n, and where I've used N for the nested list of items I've changed it to x so it's hopefully clearer that these things are not the same length. I've been using N/n interchangeably to represent an amount of things (e.g. there was n things = there were 10 things, or maybe = there were 100 things), although I appreciate now that was probably confusing. The array we receive contains a struct (mapper.Page) in each array element. The struct has a field (.URLs) which is an array of strings. $\endgroup$ – Integralist Feb 24 at 20:38
  • $\begingroup$ So on each iteration of our list we have a struct (mapper.Page) which is passed to our crawl function. The crawl function loops over the struct's .URLs field and for each element we check if we should do something with the specific URL, and if so we push the URL string into a queue to be processed (e.g. the URL is requested via a network call, the URL is put into a hash table, and finally the URL is appended to a different array) $\endgroup$ – Integralist Feb 24 at 20:48
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.