3

I came across this question for the Big O time complexity of this code snippet: It is guaranteed that the time complexity for the following code is O(n^4).

ArrayList<Integer> list = new ArrayList<Integer>();

for(int i = n; i>=1; i--)           //n 
    for(int j = 1; j<=i; j++)       //n     
        if(!list.contains(i*j))     //n?    
            list.add(i*j);          //1?

My Question: Why is it O(n^4) instead of O(n^3)?

user3437460
  • 17,253
  • 15
  • 58
  • 106
  • What's `n` initialized to? – Janus Varmarken Aug 18 '18 at 04:01
  • @JanusVarmarken This is the complete question. It doesn't matter what `n` is to determine the Big O...you can assume it as some number greater than 1. – user3437460 Aug 18 '18 at 04:02
  • I was suspecting it could be due to the `add` because arraylist are backed by array which double itself when filled and all elements have to be copied to the new array. – user3437460 Aug 18 '18 at 04:13
  • But, that would just add another constant onto the n (because the `if` is not `looping` around the `add`). – Bill Aug 18 '18 at 04:18

2 Answers2

7

list has about n^2/2 entries[*], so the lookup list.contains(i*j) is O(n^2) not O(n)

*: some less because duplicates are not added, but i guess enough to count as n^2

k5_
  • 5,450
  • 2
  • 19
  • 27
  • How does `list.contains(i*j)` gives O(n^2) here? Mind elaborating? – user3437460 Aug 18 '18 at 04:10
  • Ignoring the duplicates; at the end you will have added `(n^2)/2` entries to the list. `contains` has `O(r)` where `r` is the number of entries in list, hence `O(n^2/2) = O(n^2)` – k5_ Aug 18 '18 at 04:13
  • Nice observation! – GhostCat Aug 18 '18 at 04:47
  • @k5_ If there are 3 layers of nested for loops, all looping n number of times, in this case, the `.contains()` will be O(n^3) ? Which means the overall complexity becomes O(n^6) ? Is this the correct understanding? – user3437460 Aug 18 '18 at 15:07
0

list.contains(i*j) happens in O(n^2) as i and j are dependents on n ( if linear search is used ). Basically it will be 2 loops in O(n) nested and an operation of of O(n^2) inside the nested loop and hence O(n^4).

Prajval M
  • 2,298
  • 11
  • 32
  • 1
    `i*j` is just an integer, so it will be `list.contains(x)` where `x = i*j`. So it should just a be linear, `O(n)` lookup time. – Bill Aug 18 '18 at 04:28
  • 2
    @Bill the complexity in this case depends on the number entries in the list, not on the parameter value. – k5_ Aug 18 '18 at 04:30
  • @Bill In terms of x i.e i*j it is linear but in terms of n it is quadratic. – Prajval M Aug 18 '18 at 04:31
  • @k5_, that was my point in commenting. It should just be a linear lookup because the parameter is irrelevant. – Bill Aug 18 '18 at 04:34
  • @Bill linear to r where r is the number of entries in the list. but r is n^2 (the n from the first loop) – k5_ Aug 18 '18 at 04:35
  • 2
    @k5_, Doh! of course. I was getting my wires crossed. `O(n^2)` in this case because the list will have `n^2` elements, worst case. Sorry, my confusion. – Bill Aug 18 '18 at 04:37