All Questions
Tagged with algorithmscomplexity
70 questions
67votes
17answers
18kviews
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. How relevant is big-O analysis to development in industry? How often do you ...
41votes
2answers
18kviews
What is O(...) and how do I calculate it?
Help! I have a question where I need to analyze the Big-O of an algorithm or some code. I am unsure exactly what Big-O is or how it relates to Big-Theta or other means of analyzing an algorithm's ...
33votes
5answers
91kviews
Determining if an Algorithm is O (log n)
I'm refreshing my CS Theory, and I want to know how to identify that an algorithm O (log n) complexity. Specifically, is there an easy way to identify it? I know with O(n), you usually have a single ...
- 915
21votes
6answers
5kviews
Using a different algorithm depending on the size of the input
I recently finished a course on advanced algorithms, and another on complexity & computability theory, and in the past few days my mind has been somewhat preoccupied by this question. Why don't we ...
- 345
18votes
5answers
30kviews
What would be the Impact of P=NP? [closed]
I am preparing for a test and I can't find a clear answer on the question: What would be the impact of proving that PTIME=NPTIME. I checked wikipedia and it just mentioned that it would have "profound ...
- 437
18votes
3answers
21kviews
What does it mean by expected running time and average running time of an algorithm?
Let's say we want to analyze running time of algorithms. Sometimes we say that we want to find the running time of an algorithm when the input size is n and for the worst possible case it is denote it ...
- 5,217
16votes
4answers
4kviews
Are Constant Time and Amortized Constant Time effectively considered equivalent?
I need to write a RandomQueue that allows for appends and random removal in Constant Time ( O(1) ). My first thought was to back it with some kind of Array (I chose an ArrayList), since arrays have ...
- 2,663
11votes
5answers
918views
Programmaticaly finding the Landau notation (Big O or Theta notation) of an algorithm?
I'm used to search for the Landau (Big O, Theta...) notation of my algorithms by hand to make sure they are as optimized as they can be, but when the functions are getting really big and complex, it's ...
- 219
9votes
4answers
11kviews
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 &...
- 1,830
9votes
3answers
58kviews
What is the time complexity of the algorithm to check if a number is prime?
What is the time complexity of the algorithm to check if a number is prime? This is the algorithm : bool isPrime (int number) { if (number < 2) return false; if (number == 2) return ...
9votes
1answer
1kviews
Subset sum problem is NP-complete?
If I know correctly, subset sum problem is NP-complete. Here you have an array of n integers and you are given a target sum t, you have to return the numbers from the array which can sum up to the ...
- 1,162
9votes
5answers
8kviews
Smallest lexicographical rotation of a string using suffix arrays in O(n)
I will quote the problem from ACM 2003: Consider a string of length n (1 <= n <= 100000). Determine its minimum lexicographic rotation. For example, the rotations of the string “alabala” are: ...
- 507
8votes
2answers
2kviews
single for-loop runtime explanation problem
I am analyzing some running times of different for-loops, and as I'm getting more knowledge, I'm curious to understand this problem which I have still yet to find out. I have this exercise called "How ...
- 145
8votes
3answers
509views
How many copies are needed to enlarge an array?
I am reading an analysis on dynamic arrays (from the Skiena's algorithm manual). I.e. when we have an array structure and each time we are out of space we allocate a new array of double the size of ...
- 1,830
7votes
3answers
15kviews
Is O(log n) + O(log n) = O(n)? [duplicate]
We know that binary search takes O(log n) in Big O notation but if we need to run twice an algorithm of O(log n), would it be the same as O(n) in time complexity? For example, if I have a method to ...
- 181
