Time complexity of for loops in Java

Question

I have started learning Big O notation and analysing time complexities, and I tried messing around with some code to try and understand its time complexity. Here's one of the lines that I had, but I can't seem to figure out what the time complexity for the sum method is? I reckon it is o(n^3) but my friend says it should be o(n^2). Any insights as to what is the right answer?

public static double sum(double[] array) { double sum = 0.0; for(int k = 0; k < size(array); k++) sum = sum + get(array, k); return sum; } public static double get(double[] array, int k) { for(int x=0; x < k; x++) if(x==k) return array[k]; return -1; } public static int size(double[] array) { int size = 0; for(int k=0; k<array.length; k++) size++; return size; }

size() is O(n); get() is O(n). You are executing size() on each iteration of a loop which runs size() times; and inside the loop you execute get() on each iteration. So it's O(n^3). — Andy Turner
– Andy Turner, Commented Oct 26, 2021 at 12:54

Timur Toktassynov · Accepted Answer · 2021-10-26 13:31:04Z

1

I guess you friend is right, time complexity is O(n^2). Because on each iteration in your loop, you consequently calculate size(), which is order of O(n), and calculate get(), which on average is O(n/2). So each iteration's complexity is O(1.5 * n) and overall is O(n^2)

answered Oct 26, 2021 at 13:31

Timur Toktassynov

113 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Haardik Chopra Over a year ago

You said get is on average O(n/2), but if we are looking at worst case scenario, would it still be O(n^2)? Or am I confusing the concepts here?

Timur Toktassynov Over a year ago

So for get the worst call would be that of k = n - 1 and best would be n = 0, but usullly we just take the average which is n/2.

Collectives™ on Stack Overflow

Time complexity of for loops in Java

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related