If I have the following code, let's say the Parent class has the complexity of O(n^2) according to methods included in the Parent. So if I want to calculate the complexity of inherited class (Child class), does it take the Parent class complexity and its own complexity? something like that complexity of child class = O(O(Parent)+O(Child)) ? public class Parent { private int number; // more stuff } public class Child extends Parent { public void setNumber(int newNum){ this.number = newNum; } } |
0
21 | ||

i have created a recursive method that returns the size of a binary search tree, i would like to analyze the running time of my implementation but i dont know how. I know the best case is O(1) if node is null but what about worst case? my researches online offer conflicting information. One source says to imagine the internal stack which makes me believe O(N^2) and another says to break it up into an equation. I feel like the worst case is O(N) as each of the nodes must be accessed in order to return their value but i … |
0
35 | ||

hello everyone I was wondering if anyone could explain big-oh estimate to me for c++ data structures. I do not understand it that much and does anyone know of any good websites that have good information on c++ data structures i would greatly appreciate it. Also could anyone explain to me how to use big-oh estimate on the following problem. My prof gave this to us at the end of class saying he would explain how to do solve it the next class day but i have no idea how to do this, would greatly appreciate anyones help. thanks. the … |
0
4 | ||

Hi I need to prove the following statements: 1) for any a>1, and any b, a^n ∈ ω(n^b). We have to prove f(n) > C.g(n) for all C>0, n0>0 and n>=n0 a^n > C . n^b Since a > 1 , I think a >= n and a > b which assures that the left hand side will be always greater than the right hand side. Is that right ? 2) We have f(n)= n^2 and g(n)=42. Is f(n) ∈ O (g(n)) or f(n) ∈ Ω(g(n)) ? What I think is f(n) ∈ Ω(g(n)) n^2 >= C.g(n) n must be … |
0
3 | ||

I see that there are many questions here regarding complexity analysis, specifically regarding the Big-O notation of algorithms. I will attempt to shed some light on the subject. I will start with an introduction, after which I will go over some common complexities and last we will solve a few simple examples for practice. [U][B]1. Introduction[/B][/U] When looking at the Algorithm, we want to know its order of growth regarding the input size given to it. Consider two simple algorithms that sort an array of [TEX]n[/TEX] cells. The first algorithm is doing [TEX]n[/TEX] operations in order to complete the sort, … |
13
23 | ||

Hello everyone, it's my first time posting here and it's an urgent matter as I need the solution to this by midnight tonight :/ I'm really struggling with the all Big-Oh notation thing and I could really use your help. I have this C++ code: [CODE]void Teste::listarMaisAfastados() { int maior = 0; Utilizador maiorX, maiorY; for (int i = 0; i <= utilizadores.NumVert(); i++) { Utilizador tmpUL = utilizadores.getVerticeById(i); for(int y = 0; y <= utilizadores.NumVert(); y++) { Utilizador TmpYL = utilizadores.getVerticeById(y); int tmp = utilizadores.distancia(tmpUL, TmpYL, false); if(tmp > maior) { maior = tmp; maiorX = tmpUL; maiorY = … |
0
6 | ||

I am trying to determine the time complexity (and space complexity if anyone would like to have a go at it) of a sort function i implemented with a custom comparator. it is the sort function from the STL <algorithm>. First off, I am using Visual C++, so I am assuming it uses the standard C++ sort, which from what I have read on the web has an average complexity of N*log(N) and a worst case of N^2. Now, here is the implementation: [CODE] bool by_length (const string& s1, const string& s2) { if ( s1.length() == s2.length() ) return … |
0
4 | ||

So here's the question: Suppose as min heap uses parent pointers such that each node contains a pointer to its parent and the root has a null pointer. Given a pointer to the node, which isn't the root of the tree, containing the max key in the heap, what is the complexity for deletion? The answer is O(1) but this doesn't make sense to me. Because heaps are always balanced you can't replace the deleted node with an adjacent node you have to scale the length of the tree O(log N) to find the last entered node in the tree, … |
0
6 | ||

I have to answer with the runtime for Big O for a few examples of C++ code. I'm generally having some trouble grasping the concept of Big O but two particular problems are stumping me: [CODE]cin >> x; double n = example(x); for ( i =0; i << n; i++) { cout << i + 100; } double example(int j) { return j * j; } [/CODE] and [CODE]cin >> n; k = 1; do { j = 1; do { . . j = 2 *j; }while (j <= n); k++; }while(k <= n); [/CODE] What stumps me in … |
0
3 |

The End.