Need some java help with a question for my program. Im still fairly bad with rec

Question

Need some java help with a question for my program. Im still fairly bad with recognizing order of growth operations in programs so I am hoping you can show me the number for each

Question;

1. What is the order of growth of the number of compares (in the worst case) that each of the operations in the Autocomplete data type make, as a function of the number of terms n and the number of matching terms m?

Recall that with order-of-growth notation, you should discard leading coefficients and lower-order terms, e.g., m^2 + m log n.

a)constructor:

b)allMatches():

c)numberOfMatches():

Program

public class Autocomplete {

private Term[] arrayTerms;

// Initializes the data structure from the given array of terms.

public Autocomplete(Term[] terms) {

if (terms == null){

JOptionPane.showMessageDialog(null, "There are no terms", "No Terms", JOptionPane.ERROR_MESSAGE);

throw new NullPointerException("There are no terms");

}

this.arrayTerms = terms;

//orders the array of terms

Arrays.sort(arrayTerms);

}

// Returns all terms that start with the given prefix, in descending order of weight.

public Term[] allMatches(String prefix) {

if (prefix == null){

throw new NullPointerException();

}

Term temp = new Term(prefix, 0);

int begin = BinarySearchDeluxe.firstIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));

int end = BinarySearchDeluxe.lastIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));

if (begin == -1 || end == -1){

JOptionPane.showMessageDialog(null, "Nothing matches that term", "No Matches", JOptionPane.ERROR_MESSAGE);

throw new NullPointerException("Nothing matches that term");

}

Term[] matches = new Term[end - begin + 1];

matches = Arrays.copyOfRange(arrayTerms, begin, end);

Arrays.sort(matches, Term.byReverseWeightOrder());

return matches;

}

// Returns the number of terms that start with the given prefix.

public int numberOfMatches(String prefix) {

if (prefix == null){

JOptionPane.showMessageDialog(null, "Nothing with that prefix", "No Matches", JOptionPane.ERROR_MESSAGE);

throw new NullPointerException("Nothing with that prefix");

}

Term temp = new Term(prefix, 0);

int begin = BinarySearchDeluxe.firstIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));

int end = BinarySearchDeluxe.lastIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));

return end - begin + 1;

}

public static void main(String[] args){

// read in the terms from a file

String filename = "wiktionary.txt";

In in = new In(filename);

int N = in.readInt();

Term[] terms = new Term[N];

for (int i = 0; i < N; i++) {

long weight = in.readLong(); // read the next weight

in.readChar(); // scan past the tab

String query = in.readLine(); // read the next query

terms[i] = new Term(query, weight); // construct the term

}

// read in queries from standard input and print out the top k matching terms

int k = Integer.parseInt("10");

Autocomplete autocomplete = new Autocomplete(terms);

while (StdIn.hasNextLine()) {

String prefix = StdIn.readLine();

Term[] results = autocomplete.allMatches(prefix);

for (int i = 0; i < Math.min(k, results.length); i++)

StdOut.println(results[i]);

}

}

}

Explanation / Answer

For Finding Order of growth we should always keep in mind the portions of code which are looped or function calls which are performed by looping.

a. constructor

So if we look into the constructor code, the bold and italicised text is what contributes to time complexity or order of growth.

public Autocomplete(Term[] terms) {

if (terms == null){

JOptionPane.showMessageDialog(null, "There are no terms", "No Terms", JOptionPane.ERROR_MESSAGE);

throw new NullPointerException("There are no terms");

}

this.arrayTerms = terms;

//orders the array of terms

Arrays.sort(arrayTerms);

}

this is because Arrays.sort function uses looping internally to sort the array arrayTerms. If n is size of terms

Arrays.sort function generally has worst case time complexity of nlog(n).

Hence the order of growth for the constructor is O(nlog(n)).

b. allMatches()

The bold and italicised text contributes to order of growth.

public Term[] allMatches(String prefix) {

if (prefix == null){

throw new NullPointerException();

}

Term temp = new Term(prefix, 0);

int begin = BinarySearchDeluxe.firstIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));

int end = BinarySearchDeluxe.lastIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));

if (begin == -1 || end == -1){

JOptionPane.showMessageDialog(null, "Nothing matches that term", "No Matches", JOptionPane.ERROR_MESSAGE);

throw new NullPointerException("Nothing matches that term");

}

Term[] matches = new Term[end - begin + 1];

matches = Arrays.copyOfRange(arrayTerms, begin, end);

Arrays.sort(matches, Term.byReverseWeightOrder());

return matches;

}

both functions BinarySearchDeluxe.firstIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));

and BinarySearchDeluxe.lastIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));

have a time complexity (tc) of O(log(n))

hence tc = 2log(n)

Arrays.copyOfRange internally uses System.arraycopy whose complexity is O(n).

hence tc = O(n)

As we already know Arrays.sort has complexity of nlog(n) but here sort function is applied only for matches subset of array of size matches

hence tc = O(mlog(m))

Therefore, the order of growth of entire function is

= 2log(n) + n + mlog(m)

= O(mlog(m) + n + log(n)) (after discarding constants)

c. numberOfMatches()

public int numberOfMatches(String prefix) {

if (prefix == null){

JOptionPane.showMessageDialog(null, "Nothing with that prefix", "No Matches", JOptionPane.ERROR_MESSAGE);

throw new NullPointerException("Nothing with that prefix");

}

Term temp = new Term(prefix, 0);

int begin = BinarySearchDeluxe.firstIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));

int end = BinarySearchDeluxe.lastIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));

return end - begin + 1;

}

again both the functions BinarySearchDeluxe.firstIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));

and int end = BinarySearchDeluxe.lastIndexOf(arrayTerms, temp, Term.byPrefixOrder(prefix.length()));

have a time complexity of O(log(n))

hence order of growth = O(2log(n)) = O(log(n))

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.