CODEWITHSUNDEEP
javaperformancebig-o
Paul
Paul

Reputation: 1149

Calculating run time analysis on a few methods

I am preparing for my exam and having a little trouble on run time analysis. I have 2 methods below that I am confused on the run time analysis for:

 public boolean findDuplicates(String [] arr) {
    Hashtable<String,String> h = new Hashtable<String,String>();
    for (int i = 0; i < arr.length; i++) {
         if (h.get(arr[i]) == null)
              h.put(arr[i], arr[i]);
         else
              return true;
         }
    return false;
    }

Assuming that hash function only takes O(1) on any key, would the run time simply be O(n) due to in worst case, running through the entire array? Am I thinking of this along the right lines if each hash function takes constant time to evaluate?

The other problem I have seems much more complicated and I don't know exactly how to approach this. Assume these are arrarlists.

public boolean makeTranslation(List<Integer> lst1, List<Integer> lst2) {
//both lst1 and lst2 are same size and size is positive
     int shift = lst1.get(0) - lst2.get(0);
     for (int i = 1; i < lst1.size(); i++)
          if ( (lst1.get(i) - lst2.get(i)) != shift)
               return false;
     return true;
}

In this case, the get operations are supposed to be constant since we are simply retrieving a particular index values. But in the for loop, we are both comparing it to shift and also iterating over all elements. How exactly would this translate to run time?

A helpful explanation would be much appreciated since I have the hardest time understanding run time analysis than anything in this course and my final is next week.

Upvotes: 1

Views: 1340

Answers (4)

Makoto
Makoto

Reputation: 106430

It's worth echoing, but both of these operations are O(n) (for #2, that's the worst case). The key thing to note is the number of critical operations done each iteration through.

For your first snippet, the Hashtable is a bit of a red herring, since access time isn't going to be your largest operation in the loop. It's also the case that, since that Hashtable was just new'd, you'll always be inserting n elements into it.

For your second snippet, you have a chance to end early. If the next elements' difference isn't shift, then you return false right there and then, which was only one operation. In the worst case, you'll be going through all n and returning.

Upvotes: 0

Terry Li
Terry Li

Reputation: 17268

The short answer: both methods have time complexity of O(n).

For hash, it is clear that both get and put operations take constant time.

For list, if you use the ArrayList implementation(and it is likely), the get method takes constant time as well. This is because an ArrayList in Java is a List that is backed by an array.

Code for ArrayList.get(index) in the standard Java library:

public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}

RangeCheck probably did two comparisons, which is constant time. Returning a value from an array is obviously constant time. Thus, the get method for ArrayList takes constant time.

As for your specific concern mentioned in the OP:

But in the for loop, we are both comparing it to shift and also iterating over all elements. How exactly would this translate to run time?

lst1.get(i) takes constant time. lst2.get(i) takes constant time. Thus, lst1.get(i) - lst2.get(i) takes constant time. The same holds for (lst1.get(i) - lst2.get(i)) != shift. The idea is the sum of a constant number of constant time operations is still constant time. Since the loop iterates up to n times, the total time is O(Cn), i.e., O(n) where C is a constant.

And...it never hurts to have a brief review of the big O notation just before final :)

Upvotes: 1

ddmps
ddmps

Reputation: 4380

Big-O notation is not very accurate as you omit constant factors and lower order terms. So, even if you have 2 constant operations n times, it will still be O(n). In reality, it will be (1+1)n=2n, but in ordo-notation we round it down (even if it's 10000n). So, for both these cases the run-time will be O(n).

In practice, I suggest typing out the costs for each loop and each operation in the worst case. Start from the innermost nested level and multiply outwards (with only the highest cost of each level).

For example:

for (int i = 0; i<n; i++) { //n times
    //log n operation
    for (int i = 0; i<n; i++) { //n times
        //constant operation
    }
}

Here, we have n*(log(n)+n*1)=O(n*n) as n>log(n)

Upvotes: 0

chubakueno
chubakueno

Reputation: 565

In general, the O() expresses the complexity of an algorithm wich generally is the number of operations, assuming the cost of each operation is constant.For example O(1000n) would be the similar to writing O(n), because each operation costs 1000, and there are n operations.

So assuming get and put are constant (depends on library implementation) for every value, the time for both would be O(n). For more information see: http://en.wikipedia.org/wiki/Big_O_notation

Upvotes: 0

Related Questions