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:
- defines a worker pool size
- pushes tasks into a channel
- 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
andMapper
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
- pass each struct within the collection to
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
- if url already tracked in hash table:
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).
n
in another place. If you intend those to represent the same thing, you should use the same variable for both consistently. $\endgroup$