1
vote
2answers
183 views

What is a O(n) algorithm to solve this puzzle?

We are going to hold a meeting where everybody will speak in clockwise direction around a table. There are n people with n spots. Each person has a position preference (e.g. some want to go first, ...
0
votes
4answers
275 views

Binary Search seems superior, why did the committee of C++ still have Find in the algorithm library?

I wish to search for an integer in a vector of integer. I have two candidates for the job: Binary Search Find It seems that Binary Search is the best candidate for the job as although I have to ...
0
votes
3answers
438 views

Time-complexity of nested for loop

I have loops like this: for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { sum += 1; } } It's O(n * ), but I'm not sure what the j < i loop is. I have some tests ...
2
votes
5answers
345 views

Find pattern in a string

How would one approach the following question: We have two strings: a normal alphanumeric string and a pattern string. the pattern string can be composed by alphanumeric chars plus the char "?" and ...
0
votes
4answers
105 views

Big-O of this algorithm?

How can I describe the growth function in terms of n for the following algorithm? What is the bounding function (the Big-O)? Is it O(n^3)? for(i = 0 to n - 1) { c = i + 1 for(j = c to n) ...
7
votes
3answers
337 views

Change of the complexity class through compiler optimization?

I am looking for an example where an algorithm is apparently changing its complexity class due to compiler and/or processor optimization strategies.
14
votes
4answers
1k views

Is this a Proper “Rule” for Identifying the “Big O” Notation of an Algorithm?

I've been learning more about Big O Notation and how to calculate it based on how an algorithm is written. I came across an interesting set of "rules" for calculating an algorithms Big O notation and ...
0
votes
1answer
173 views

Help with algorithmic complexity in custom merge sort implementation

I've got an implementation of the merge sort in C++ using a custom doubly linked list. I'm coming up with a big O complexity of n^2, based on the merge_sort() > slice operation. But, from what I've ...
11
votes
3answers
727 views

Please explain the statement that the function an+b belongs to O(n^2) and and Θ(n)?

Let's say I have a linear function f(n)= an+b, what is the best way to prove that this function belongs to O(n2) and Θ(n)? I do not need mathematical rigor here. I need a programmers answer. Some ...
3
votes
3answers
330 views

questions on a particular algorithm

Upon searching for a fast primr algorithm, I stumbled upon this: public static boolean isP(long n) { if (n==2 || n==3) return true; if ((n&0x1)==0 || n%3==0 || n<2) return false; ...
1
vote
1answer
250 views

What is O(…) and how do I calculate it? [closed]

Possible Duplicate: Plain English explanation of Big O I've seen some questions here and on SO talking about the most efficient way to find or sort this or that. The questions usually talk ...
2
votes
1answer
683 views

Best Upper Bound & Best Lower Bound of an Algorithm

I am studying for a final exam and I came past a question I had on an earlier test. The questions asks us to find the minimum value in an unsorted array of integers. We must provide the best upper ...
37
votes
20answers
3k views

Do real-world algorithms that greatly outperform in the class below exist?

Last night I was discussing with another programmer that even though something may be O(1), an operation which is O(n) may outperform it if there are is a large constant in the O(1) algorithm. He ...
2
votes
6answers
1k views

Why is the formal definition of Big O notation formulated as such?

Consider the formal definition: f(n) = O(g(n)) Why is it not: f(n) = O(f(n)) or f(n) = O(c*f(n)) since for the Big O analysis, f(n)=2n and g(n)=n are identical? I am ...
5
votes
4answers
2k views

Big-O for nested loop

I am reading this post on Big-O It says that the following code is O(n^2): bool ContainsDuplicates(String[] strings) { for(int i = 0; i < strings.Length; i++) { for(int j = 0; j ...
46
votes
16answers
3k views

Is big-O really that relevant when working in industry?

In every interview I have been in, I have been quizzed on mathematical analysis of complexity, including big-O notation. My question is, how relevant is this test to development in industry? How often ...