The Big-O notation is used to represent asymptotic upper bounds. It describes relevant time or space complexity of algorithms. Big-O analysis provides a coarse and simplified estimate of a problem difficulty.

learn more… | top users | synonyms

1
vote
2answers
180 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
274 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 ...
2
votes
1answer
130 views

How this Fibonacci exponentiation by squaring algorithm works?

This is one of the best algorithms to calculate the nth Fibonacci sequence. it needs O(log(n)) time to do its job, so it's so efficient. I found it somewhere but don't know how it works! Can anyone ...
0
votes
3answers
405 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 ...
-4
votes
1answer
546 views

What is the big-O cpu time of Euclid's Algorithm of “Greatest common divisor of two numbers”

Looking at Euclid's algorithm for the "Greatest common divisor of two numbers", I'm trying to divine the big-O cpu time for numbers K, and N. Can anybody help? This is the algorithm as I understand ...
2
votes
5answers
344 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) ...
2
votes
1answer
235 views

What exactly is “big O” notation? [duplicate]

From what I've gathered, big O notation is used to describe the length of an operation. However, that's as far as I've gotten. What exactly is big O notation and how do the most common ones (O(n), ...
0
votes
1answer
51 views

clarification about amortized analysis

I was going through an article here In the section named Aggregate Method ,the author says Then summing over the entire sequence, all the 1's sum to O(n), and all the di also sum to O(n). That ...
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.
1
vote
1answer
274 views

Notation for the average time complexity of an algorithm

What notation do you use for the average time complexity of an algorithm? It occurs to me that the proper way would be to use big-theta to refer to a set of results (even when a specific try may ...
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 ...
1
vote
2answers
172 views

Constants and Big O [duplicate]

Are constants always irrelevant even if they are large? For example is O(10^9 * N) == O(N) ?
7
votes
1answer
1k views

Problems Calculating Big-O Complexity

I'm a complete beginner to Java, only in my second quarter of classes. I'm having trouble understanding our current chapter about calculating big-O for methods. So I thought I was right in saying that ...
0
votes
1answer
172 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 ...
10
votes
7answers
2k views

Big Oh notation does not mention constant value

I am a programmer and have just started reading Algorithms. I am not completely convinced with the notations namely Bog Oh, Big Omega and Big Theta. The reason is by definition of Big Oh, it states ...
11
votes
3answers
724 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
329 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
678 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 ...
49
votes
14answers
7k views

Get 100 highest numbers from an infinite list

One of my friend was asked this interview question - "There is a constant flow of numbers coming in from some infinite list of numbers out of which you need to maintain a datastructure as to ...
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 ...
13
votes
7answers
2k views

What is O in Big O?

What is Big and O in Big O notation? I've read the definitions and it doesn't tell what is O pronounced as 'oh'. For example - I understand that O(n) is complexity of a linear algorithm where n could ...
17
votes
2answers
2k views

Why is Big O taught instead of Big Theta?

Big O notation provides an upper bound to a function whereas Big Theta provides a tight bound. However I find that Big O notation is typically (and informally) taught and used when they really mean ...
15
votes
6answers
2k views

How do I determine the runtime of a double recursive function?

Given any arbitrarily double-recursive function, how would one calculate its run time? For Example (in pseudocode): int a(int x){ if (x < = 0) return 1010; else return b(x-1) + ...
1
vote
5answers
397 views

BIG O - Algorithm Case Analysis

Why is big O most commonly associated with worst and average case complexties of a function
4
votes
6answers
2k views

Proper way to “say” Big-O notation?

What is the proper way to convey an algorithm complexity in Big-O notation in speech? Dose "the total number of operations is big oh of N log N" sounds strange? What's generally accepted: "It have ...
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 ...