For binary search tree type of data structures, I see the Big O notation is typically noted as O(logn). With a lowercase 'l' in log, does this imply log base e (n) as described by the natural logarithm? Sorry for the simple question but I've always had trouble distinguishing between the different implied logarithms. ...
When I analyzed the complexity of the code segment below, I found that it is O(n/2). But while searching the internet I discovered that it is probably O(n). I'd like to know who's correct. void function(int n) { int i = 1, k = 100; while (i < n) { k++; i += 2; } } ...
Assume that methods m1 and m2 are static void and compute the same result by processing an argument of type Object[]. Empirically we find that m1 -> T(N) = 100N and m2 -> T(N) = 10Nlog2N where the times are in microseconds. For what size inputs is it better to use m1 and m2? So I would use m1 for big numbers while I would use m2 for sma...
hi, i need to insert into a very large LinkedList, whose elements i hold in a fast-access HashMap. it's important to keep the list in order (which is not the natural order of the keys). i thought it would be possible to hash the linked list nodes, then insert directly on the node (getting the node from the map + insert in a linked list...
I know that planarity testing can be done in O(v) (equivalently O(e), since planar graphs have O(v) edges) time. I wonder if it can be done online in O(1) amortized time as each edge is added (still O(e) time overall). In other words, in a database table representing edges of a graph and subject to a constraint that the represented gra...
Let's say that you have a list of 10,000 email addresses, and you'd like to find what some of the closest "neighbors" in this list are - defined as email addresses that are suspiciously close to other email addresses in your list. I'm aware of how to calculate the Levenshtein distance between two strings (thanks to this question), which...
hey there could someone please help me determine the complexity?. An example given in my class was bubble sort int main() { int a[10] = {10,9,8,7,6,5,4,3,2,1}; int i,j,temp; for (j=0;j<10;j++) { for (i=0;i<9;i++) { if (a[i] > a[i+1]) { temp = a[i]; a[i] = a[i+1]; a[i+1] = te...
Got this question in an interview today, and its optimized solution stopped me cold (which blows, because I really wanted to work for this company...) Given a single array of real values, each of which represents the stock value of a company after an arbitrary period of time, find the best buy price and its corresponding best sell price...
Hello I just have a simple question, why is the big O notation of a sorted array O(log N)? It will be a sorted array. ...
G'day, Edit: While this question covers a situation that can arise in programming a lot, i have always noticed that there is a point when working with regex's, esp. in Perl and with shell-programming, where trying to capture those last few edge cases: requires much, much more time to expand your regex, which can mean excessive complex...
I have need to do some cluster analysis on a set of 2 dimensional data (I may add extra dimensions along the way). The analysis itself will form part of the data being fed into a visualisation, rather than the inputs into another process (e.g. Radial Basis Function Networks). To this end, I'd like to find a set of clusters which prim...
My team is building a product that has a lot of components that rely on each other. For example, whenever we add a new type of data to the system, we also have to add logging code to track the changes that use that data type. Or, when we add a new UI screen, we have to make sure that its strings are externalized so they can be translated...
procedure max (a[1..n]: integers) max := a[1] for i := 2 to n if max < a[i] then max := a[i] Is the complexity O(1) or O(n) with the best case scenario? The sequence contains n elements. It is pseudocode. ...
I started toying with this idea some years ago when I wrote my university papers. The idea is this - the perfect color quantization algorithm would take an arbitrary true-color picture and reduce the number of colors to the minimum possible, while maintaining that the new image is completely indistinguishable from the original with a nak...
Wikipedia says on A* complexity the following (link here): More problematic than its time complexity is A*’s memory usage. In the worst case, it must also remember an exponential number of nodes. I fail to see this is correct because: Say we explore node A, with successors B, C, and D. Then we add B, C, and D to the list of ...
This might sound like a stupid question, but I had a long talk with some of my fellow developers and it sounded like a fun thing to think of. So; what's your thought - what does a Regex look like, that will never be matched by any string, ever! Edit: Why I want this? Well, firstly because I find it interesting to think of such an expre...
What is the complexity of inserting into sorted link list in big-O notation? Let say I have 5 elements and what is the complexity to insert all of them. Thank you very much ...
In Prolog, problems are solved using backtracking. It's a declarative paradigm rather than an imperative one (like in C, PHP or Python). In this kind of languages is it worth to think in terms of complexity? The natural way you think problems seems to be O(N^2) as someone pointed in this question. ...
What is the fastest algorithm that exists up with to solve a particular NP-Complete problem? For example, a naive implementation of travelling salesman is O(n!), but with dynamic programming it can be done in O(n^2 * 2^n). Is there any perhaps "easier" NP-Complete problem that has a better running time? I'm curious about exact solutions...
Brief: When academic (computer science) papers say "O(polylog(n))", what do they mean? I'm not confused by the "Big-Oh" notation, which I'm very familiar with, but rather by the function polylog(n). They're not talking about the complex analysis function Lis(Z) I think. Or are they? Something totally different maybe? More detail: Mos...