Member Avatar

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 …

Member Avatar
+0 forum 8
Member Avatar

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 …

Member Avatar
+0 forum 2
Member Avatar

How to calculate time complexiy of the following line of code using 'Big-O' or 'Big-OH' notation??? 1. scanf("%d",&n); 2. for(i=1,m=n+66;i<=m;i++) 3. printf("%d \n",i); 4. for(j=n/21,m=n/5;j<=m;j++) 5. printf("%d \n",j); I have basic idea but i am getting confused...So, please help me to calculate time complexity of each step, plus overall complexity. i have gone through some books and sites but, the explanation is very complex......:( And according to me the time comlexity of each step is, 1. 1 2. 1+1+(m+1)+(m) // may be true or not 3. 1 4. O(log n) // i know this is wrong 5. 1 PLEASE, correct …

Member Avatar
+0 forum 4
Member Avatar

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 = …

Member Avatar
+0 forum 5
Member Avatar

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 …

Member Avatar
+0 forum 3
Member Avatar

I've been working on getting the Big-Oh notation for this code segment a couple days now and I can't figure it out. I've most likely come across the right answer but I can't convince myself it's right. What's the Big-Oh notation for the following code and how do you arrive at that answer? [CODE=c++] x = 1; for (int i = 0; i < n -1; i++) { for (int j = 1; j <= x; j++) cout << j << endl; x *= 2; } [/CODE] My work so far: inner loop: executes x+1 times ; outer loop: n-2 …

Member Avatar
+0 forum 13
Member Avatar

Hey folks :) I am studying for my final exam, and I have some issues with this Big Oh notation. Really - I've been reading about it like crazy, but I just can't to understand it all properly. What I know is that it is some kind of measurement of growth rate. How much time it takes for a certain input to be computed. And I can't seem to grasp how it really is measured with loops. If I have a loop like this: for(int i = 0; i < 10; i++) do this... then I know it's the problem …

Member Avatar
+0 forum 10
Member Avatar

I need help in determining,using Big-O notation, the upper-bound for these two algorithms i wrote. They both do the same thing but are coded differently. They both look for all the prime numbers up to some limit, N. This first algorithm: [CODE] public static void algo1(){ primes = new int[n]; int counter = 0; for(int i=2; i<=n; i++){ prime=1; for(int j=2; j<i; j++){ if(i%j==0){ prime=0; } } if(prime==1){ primes[counter] = i; counter++; } } /** Print out Prime list */ for(int i =0; i< primes.length; i++){ if(primes[i]!=0){ System.out.println(primes[i]); } } }[/CODE] The second algorithm is suppose to be more efficient …

Member Avatar
+0 forum 3

The End.