in Education by
I recently had an interview and was given a small problem that I was to code up. The problem was basically find duplicates in an array of length n, using constant space in O(n). Each element is in the range 1-(n-1) and guaranteed to be a duplicate. This is what I came up with: public int findDuplicate(int[] vals) { int indexSum=0; int valSum=0; for (int i=0; i< vals.length; i++) { indexSum += i; valSum += vals[i]; } return valSum - indexSum; } Then we got into a discussion about the runtime of this algorithm. A sum of series from 0 -> n = (n^2 + n)/2 which is quadratic. However, isn't the algorithm O(n) time? The number of operations are bound by the length of the array right? What am I missing? Is this algorithm O(n^2)? JavaScript questions and answers, JavaScript questions pdf, JavaScript question bank, JavaScript questions and answers pdf, mcq on JavaScript pdf, JavaScript questions and solutions, JavaScript mcq Test , Interview JavaScript questions, JavaScript Questions for Interview, JavaScript MCQ (Multiple Choice Questions)

1 Answer

0 votes
by
The fact that the sum of the integers from 0 to n is O(n^2) is irrelevant here. Yes you run through the loop exactly O(n) times. The big question is, what order of complexity are you assuming on addition? If O(1) then yeah, this is linear. Most people will assume that addition is O(1). But iwhat if addition is actually O(b) (b is bits, and in our case b = log n)? If you are going to assume this, then this algorithm is actually O(n * log n) (adding n numbers, each needs log n bits to represent). Again, most people assume that addition is O(1).

Related questions

0 votes
    I recently had an interview and was given a small problem that I was to code up. The problem was ... JavaScript Questions for Interview, JavaScript MCQ (Multiple Choice Questions)...
asked Feb 25, 2022 in Education by JackTerrance
0 votes
    I recently had an interview and was given a small problem that I was to code up. The problem was ... JavaScript Questions for Interview, JavaScript MCQ (Multiple Choice Questions)...
asked Feb 24, 2022 in Education by JackTerrance
0 votes
    You have run the association rules algorithm on your dataset, and the two rules {banana, apple} => {grape} and {apple, ... have been found to be relevant. What else must be true?...
asked Apr 27, 2021 in Technology by JackTerrance
0 votes
0 votes
    Suppose we run the multistage algorithm on the data of exercise 6.3.1, with the same support threshold of 4. ... set of candidate pairs Select the correct answer from above options...
asked Nov 28, 2021 in Education by JackTerrance
0 votes
    c) A computer system was designed to have a good latest processor and I/O devices, however the designer of the ... in support of your Select the correct answer from above options...
asked Nov 28, 2021 in Education by JackTerrance
0 votes
    Locks on buffer blocks are unrelated to locks used for concurrency-control of transactions, and releasing ... Management topic in portion Recovery System of Database Management...
asked Oct 10, 2021 in Education by JackTerrance
0 votes
    Find the wrong sentence. (1) Women do not have the right to vote in Saudi Arabia. (2) PRI (Institutional ... to vote in Fiji. Select the correct answer from above options...
asked Aug 3, 2022 in Education by JackTerrance
0 votes
    Which of this package is used for analyzing code during run-time? (a) java.applet (b) java.awt (c) ... Interfaces & Packages of Java Select the correct answer from above options...
asked Feb 23, 2022 in Education by JackTerrance
0 votes
    Which of this package is used for analyzing code during run-time? (a) java.applet (b) java.awt ( ... JavaScript Questions for Interview, JavaScript MCQ (Multiple Choice Questions)...
asked Oct 24, 2021 in Education by JackTerrance
0 votes
    "At the same time this visibility does not mean popularity." Explain Select the correct answer from above options...
asked Aug 3, 2022 in Education by JackTerrance
0 votes
    Sarika is working on Writer for the first time. She does not have any reference book to read the features or ... to press plz help Select the correct answer from above options...
asked Dec 24, 2021 in Education by JackTerrance
0 votes
    Which algorithm chooses the page that has not been used for the longest period of time whenever the page ... recently used algorithm d) counting based page replacement algorithm...
asked Oct 27, 2022 in Education by JackTerrance
0 votes
    A __________is a grouping of cells that run from the left to right of a page. Select the correct answer from above options...
asked Dec 1, 2021 in Education by JackTerrance
...