I'm having a bit of trouble fully grasping Big-Oh notation and while I saw some answers for If statements, I did not see anything with method calls within if/else statements. I'm posting the relevant code below, the linear and binary searches are standard implementation (I could have used the Arrays class but chose to practice coding them myself). Both precise and general Big Oh notation would be helpful. I've made an attempt below.
public static int count(int[][] myArray, int query)
{
queryHits = 0; -----> O(1)
queryNumber++; -----> O(1)
int subArraymin; -----> O(1)
int subArraymax; ----> O(1)
int foundIndex = -1; -> O(1)
int j = 5000; -----> O(1)
for (int i = 0; i<5000; i++) ------------>O(5000 * O(?)
{
subArraymin = myArray[0][j]; -------> O(1)
subArraymax = myArray[999][j]; ------> O(1)
if (query >= subArraymin && query <= subArraymax) ----> O(1?)
{
foundIndex = binarySearch(myArray,0 , 1000, query, j); -->O(5000?) * O(log n)
if (foundIndex == -1) --> O(1?)
{
//irrelevant code omitted
}
else
{
linearSearch(myArray, query, foundIndex, j); -----> O(5000?) * O(n)
}
}
else //irrelevant code omitted
}
return queryHits;
}
My main questions:
1. Are my if statements O(1) or O(n)? 2. I believe that my for loop is O(5000 * the body of the loop) but since I'm calling two different methods, do those methods' big oh's get multiplied first?
Thank you for any help/pointers!
Aucun commentaire:
Enregistrer un commentaire