Time complexity of a recursive function containing for loop

Question

What is the time complexity(O) of this function? I have mergesort and binary search in my code as well. I know binary search is O(log n) and mergesort is O(nlogn) but what is the complexity of this algorithm?

import os

mydatafile = open("myss.csv","w+")
def rec(searchpath):
    if os.path.isdir(searchpath):
        for i in os.listdir(searchpath):
            childpath = os.path.join(searchpath,i)
            if not os.path.isdir(childpath):
                mydata = i + ", " + childpath + "\n"
                mydatafile.write(mydata)
            else:
                mydata = i + ", " + childpath + "\n"
                mydatafile.write(mydata)
                rec(childpath)
rec("C:\Python27")
mydatafile.close()

http://stackoverflow.com/questions/2709106/time-complexity-of-a-recursive-algorithm — dwbartz, Sep 19 '16 at 18:08

score 1 · Answer 1 · answered Sep 19 '16 at 18:07

1

The I/O functions somewhat mask the input. You might think that the name of the root directory searchpath is the input, but it's more reasonable to think of the input as being the rooted tree that represents the the directory hierarchy. Assuming (again, reasonably) that a constant amount of work is done at each node, the running time is just O(n).

answered Sep 19 '16 at 18:07

chepner

497,756
71
530
681

So it means my time complexity will be nlogn for my whole code since i have mergesort and binarysearch as well? – Muhammad Salman Abbasi Sep 19 '16 at 18:10
That depends on what you are sorting and searching. If you sort the resulting data file once (or at most a constant number of times), that's still O(n lg n). Each binary search is O(lg n), so if you do `k` searches (where `k` and `n` are independent), you end up with O(n lg n + k lg n). (Which basically says that the total running time is bounded whichever takes longer, the sorting or the searching.) – chepner Sep 19 '16 at 18:20

Time complexity of a recursive function containing for loop

1 Answers1