What time complexity (big o) is this specific web crawler implementation?
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. 143
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. 743