Complexity analysis for code

Question

so I wrote some Java code to list files in a directory and its sub-directories that were modified today. I need a little help understanding the time and space complexity.

The code:

public class FileInDir {

File[] files = null; 
Date d = new Date(); 
long mill;

public void listTodayFiles(String path) {
    File dir = new File(path);
    files = dir.listFiles();

    for(File file : files){
        mill = file.lastModified(); 
        Date f = new Date(mill);

        if(f.getDate() == d.getDate()){
            if(file.isFile())
                System.out.println("FILE: " + file.getName() + " WAS LAST MODIFIED ON: " + f);
            else if(file.isDirectory())
                listTodayFiles(file.getAbsolutePath());
        }
    }
}

}

So from what I understand, storing all the files into the array takes O(n) time, the loop takes O(n) time. I'm unsure about the complexity for the recursive call. I'm also unsure if the if statement plays a role in time or space complexity. Also will the space complexity be O(n) because it needs to store each element (file).

Thanks :D

possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Suma, Feb 04 '15 at 17:54

score 1 · Accepted Answer · answered Dec 23 '14 at 10:41

1

Your complexity depends on what you choose for n. If n is the number of files, the complexity is O(n) because each file is visited once.

answered Dec 23 '14 at 10:41

wvdz

16,251
4
53
90

score 0 · Answer 2 · answered Dec 23 '14 at 10:44

0

Time complexity as defined by @popovitsj is correct.

Your space complexity is also O(n) since you need to store each file object in the stack due to recursive calls.

answered Dec 23 '14 at 10:44

Sushant Tambare

526
2
9

suppose there are multiple levels of directories. then also is it same?? – Prashant Dec 23 '14 at 10:54
What if my directory only consists of files meaning that I don't need to do the recursive call, does this affect the space complexity. Also will having sub-directories affect the time complexity because I will have to visit each file within the sub-directory. – Mohamed Qulateen Dec 23 '14 at 10:57
@Prashant it's worst case scenario where I am saying that there are multiple level of directories or it's same directory with "n" number of files. space complexity will always remain same since you are creating that many file objects. – Sushant Tambare Dec 23 '14 at 11:01
How is it storing each file array in the stack when `files` object is a class variable? – boxed__l Dec 23 '14 at 11:09
@boxed__l Ya sorry. Objects are stored in heap and still it's using a memory. so complexity will remain same right? – Sushant Tambare Dec 23 '14 at 11:12
File dir and File file both are there and also File Array is there so that might took large space... – Prashant Dec 23 '14 at 12:17
I posted the question on another forum and I learned that because the recursive call is within the for loop, it makes the complexity O(n^2) _I believe this is in the worst case_. Any thoughts? – Mohamed Qulateen Dec 24 '14 at 10:59
In your case I don't think space complexity depends on for loop and recursive call. that will be a time complexity which again wrong since you are not doing like same folder recursively called again which will lead to OutOfMemory.. I don't agree on it. – Sushant Tambare Dec 24 '14 at 11:44

Complexity analysis for code

2 Answers2