Calculating run time analysis on a few methods

Question

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.

score 1 · Accepted Answer · edited May 23 '17 at 10:34

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 :)

Much thanks, I'm glad at least I was thinking along the right lines then. So no matter how many O(n) operations there are, if they are not nested within each other, the overall complexity will still be O(n) — Paul, Dec 05 '12 at 04:13

ddmps · Answer 2 · 2012-12-05T01:53:08.547

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)

chubakueno · Answer 3 · 2012-12-05T01:36:11.813

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

score 0 · Answer 4 · answered Dec 05 '12 at 03:23

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.

Calculating run time analysis on a few methods

4 Answers4