Give a runtime for the following in Big-O.public void foo(Set<Integer> aSet) { int count = 0; for (int i = 0; i < aSet.size(); i++) { if (aSet.contains(i)) { count++; } }}Group of answer choicesO(n^3)O(1)O(n log n)O(n)O(n^2)
Question
Give a runtime for the following in Big-O.public void foo(Set<Integer> aSet) { int count = 0; for (int i = 0; i < aSet.size(); i++) { if (aSet.contains(i)) { count++; } }}Group of answer choicesO(n^3)O(1)O(n log n)O(n)O(n^2)
Solution
The runtime for the given code is O(n^2). This is because the for loop runs n times (where n is the size of the set) and for each iteration, the contains method is called which also has a time complexity of O(n) in the worst case scenario for a set. Therefore, the total time complexity is O(n*n) = O(n^2).
Similar Questions
What is the time complexity of the following code fragment?for(i=1; i<n; i= i*2) a[i]=0; Group of answer choicesO(n/2)O(n^(1/2))O(n^2)O(log n)
The search algorithm that gives an overall time complexity of O(log i) + O(log n) isGroup of answer choices
What is the time complexity of searching for an element in a singly linked list?Group of answer choicesO(n)O(1)O(n log n)O(log n)
In an array-based implementation of a linear list, what is the time complexity of accessing an element at a given index?Group of answer choicesO(n)O(1)O(log n)O(n log n)
An algorithm iterates 10 times for an input of size n. What is the best-case time complexity?Group of answer choicesO(n)O(1)O(n^10)O(log n)
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.