I have a bit of code and need to write a recurrence relation for it. The code simply calculates 2 raised to the nth power. Any help is appreciated. public static int two(int n) { if (n==0) { return 1; } else if (n%2 == 0) { int x = two(n/2); return x*x; } else { return 2 * two(n-1) } ...
When reasoning about runtime cost in a garbage collected language, what is the cost of a statement such as myList = null; in terms of 'n' (the number of elements in the list)? For sake of argument, consider the list to be a singly linked list of reference types with no finalisation required. More generally, I'm looking for any informat...
If I have an array of 1 million integers. Summing it up is considered O(n) because I have to perfom n-1 add operations. Correct ? ...
I know that the relation n = Big-O(1) is false. But if we use induction involving Big-O it can be proved. But the fallacy is we cannot induct Big-O. But my question is how we can disprove the relation by using the constants. The false proof is here, please give me the proof of it being false using the constants. I'm getting confused wit...
The recursive function defined as so: function factrec($x) { if($x <= 1) { return $x; } else { return $x * factrec($x - 1); } } And iterative here: function factiter($x) { $y = $x; while($y > 1) { $x *= ($y - 1); $y--; } return $x; } I had read that on the recursive functi...
I have come across the term O(log* N) in a book I'm reading on data structures. What does log* mean? I cannot find it on Google, and WolframAlpha doesn't understand it either. ...
Can some help me with a function which is Big O(1) but not Ω(1) and the other way around? Some explanation would greatly help. ...
Hi everyone. If I am given a certain set of numbers (which I store in a balanced binary search tree for easiness), then I want to answer a query that requires me to inform what is the ith smallest number between [A,B], what would be a fast algorithm to perform that task? Technically I could traverse the tree from the root searching for...
How can I prove mathematically that 1/n is O(1)? I'm confused on where to start. Any help? ...
Hi, I'm rather new to programming and have recently been introduced to the topic of asymptotic complexity. What I'm curious about is how to figure out the asymptotic complexity of a sorting method, given the number of elements and the time taken to sort them. Here is an example of what I mean. Time for 'sortArray' to sort sorted arra...
The postage stamp problem is a mathematical riddle that asks what is the smallest postage value which cannot be placed on an envelope, if the letter can hold only a limited number of stamps, and these may only have certain specified face values. For example, suppose the envelope can hold only three stamps, and the available stamp values...
What's the big O for JavaScript's array access when used as a hash? For example, var x= []; for(var i=0; i<100000; i++){ x[i.toString()+'a'] = 123; // using string to illustrate x[alpha] } alert(x['9999a']); // linear search? One can hope JS engines will not use a linear search internally O(n), but is this for sure? ...
Hello! I need to find the complexity of finding all the cycles in a undirected graph consisting of 50 nodes. Moreover, if the graph grows large, will the complexity be changed and what will be it if the network grows considerably large. In addition, if I find only few cycles then how do I find the complexity of finding few cycles in a g...
if T(n) is O(n), then it is also correct to say T(n) is O(n2) ? ...
For some reason im unable to solve this. what will be the Big-o Notation for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { c[i][j] = 0; for (int k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; } ...
I think the Big-O notation is n^2, but im not too sure. for (int i = 0; i < n -1; i++) { for (int j = 0; j < n – 1; j++) if (x[j] > x[j+1]) { temp = x[j]; x[j] = x[j+1]; x[j+1] = temp; } } ...
while (n >= 1) n /= 2; I am unable to get the Big-O notation for this ...
Hi, Is there any tool which would tell me how efficient my code is in terms of Big Oh notation? It can either be a tool for Visual Studio (2010) or standalone. Thanks ...
While answering to this question a debate began in comments about complexity of QuickSort. What I remember from my university time is that QuickSort is O(n^2) in worst case, O(n log(n)) in average case and O(n log(n)) (but with tighter bound) in best case. What I need is a correct mathematical explanation of the meaning of average compl...
So let's say we have a function such as 6wn^2 - 6wn + 6w, would the big-o notation be O(n^2) or O(wn^2)? The problem set question asks me to write this function in Big-O form in terms of w and n, so I think it's the second one but I've never seen a big O notation like that involving 2 terms so I'm a little confused. ...