Hi guys i had a confusion for a long time on time complexity for two code snippets
For instance lets take a list , that list has n items but in the next line I initialize it to a new instance of ArrayList.
List<Integer> temp = List.of(1,2,3,4,5);
temp = new ArrayList<>(); // I believe the time complexity is O(1)
So guys in the above snippet is it really O(1) coz it creates a new instance object and points to it or am i wrong here?
The other snippet is
int counter = any value;
for(int i = 0;i<n;i*=counter)// I guess its O(n)
In the above snippet i guess its O(n) coz counter is variable and can have any random value which is not fixed or is it log(n) ?
Please do throw some light on this guys, Thanks.
- So guys in the above snippet is it really O(1) coz it creates a new instance object and points to it or am i wrong here?
Line 1 List<Integer> temp = List.of(1,2,3,4,5) is O(n). Under the hood, Java actually iterates through the elements to do null checks before setting them into the underlying array held by the List.
Line 2 temp = new ArrayList<>() is O(1). The amount of time it takes to initialize the new list is constant; there is no variable here.
When you consider the entire snippet as a whole (Lines 1 + 2 together), it is O(n), because we always take the highest complexity in the algorithm.
- In the above snippet i guess its O(n) coz counter is variable and can have any random value which is not fixed or is it log(n) ?
Given that you initialized the loop as i = 1 instead, and that both n and counter are variables and not constants, the time complexity would be O(log counter n).
In the loop, the amount of iterations left is reduced(divided) by a factor of counter after each iteration. Hence the time complexity is logarithmic. You can think of "log c n" as saying "starting with n, the number of times you need to recursively divide by c in order to reach 1".
However, if you really meant to initialize the loop as i = 0, it would just execute infinitely.