CODEWITHSUNDEEP
javaarraystime-complexitybig-o
Haardik Chopra
Haardik Chopra

Reputation: 87

Time complexity of for loops in Java

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;
   
}

Upvotes: 0

Views: 296

Answers (1)

Timur Toktassynov
Timur Toktassynov

Reputation: 11

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)

Upvotes: 1

Related Questions