This is for my computer science class. For my next assignment I've got some questions similar to the following, and I'm having trouble figuring out how I would go about doing them, exactly. Question 1: Algorithm A executes 10n log n operations while Algorithm B executes n 2 operations. Determine the minimum integer value n 0 such that A executes fewer operations than B for n >= n 0. Is there a way to set up equations to compare the two? Or is there something else to it that I'm not seeing? There are no examples similar to this in my book so I'm kind of lost as far as direction.. A point in the right direction is all I'm looking for. Thanks..

Do you have a graphing calculator or mathmatica? Graph n^2 against 10n*logn, find the point that they cross

Ahh.. Yes, thank you! I knew it would be something with finding their intersections but I was unsure of how to do it. Would the same process work for this one? b)The number of operations executed by algorithms A and B is 8n log n and 2n^2, respectively. Determine n0 such that A is better than B for n >= n0. And so forth..? I've got a couple of these to answer and want to make sure .. The wording of them is what mixes me up.

This isn't my algorithms class .. That's next semester. I just wish my teacher did more than go through slides and tell us to read the book, then assign stuff that was not explained by the book or the slides

actually after messing around with it, it's just better to plot two different lines and find the intersection, the solution for that equation is not very simple! you can however simplify it to 4*log(n) = n n = 8.613169456

Here's my next problem .. Got a little confused here about calculating run times. Analyze its worst-case running time and express it in “Big Oh” notation. Algorithm [FONT="]Foo[/FONT](a, n): Input: two integers, a and n Output: a^n k [FONT="]← [/FONT]0 b [FONT="]←[/FONT] 1 while k < n do k [FONT="]←[/FONT]k + 1 b [FONT="]←[/FONT]b * a end while return b I know that I need to count how many times each step will be performed, but how do I calculate it in terms of n? It looks to me like the steps inside the while loop will run (N+1) times, but how do I calculate the rest of the steps? Any help would be great..

the stuff in the loop will run n times, so if you consider b<- b*a to be your basic operation then then runtime in terms of n would be t(n) = n. that would be your worst case and you every case as it would be the same everytime depending on n. so you could say the big oh runtime is O(n) which means that the complexity category of this algorithm is <= n

hm.. I see what you did, and it makes sense. However, I've got other problems that are very similar and I'm having difficulty understanding the process. Perhaps I can post it, break down what I think is correct and you can guide me through it? Here's the next algorithm (it performs the same task, so clearly the runtime is intended to be different).. Algorithm [FONT="]Bar [/FONT](a, n): [FONT="]Input[/FONT][FONT="]: two integers, a and n[/FONT] [FONT="]Output: ?[/FONT] [FONT="]k ← n [/FONT] [FONT="]b ← 1[/FONT] [FONT="]c ← a[/FONT] [FONT="]while k > 0 do[/FONT] [FONT="]if k mod 2 = 0 then[/FONT] k [FONT="]←[/FONT]k / 2 c [FONT="]←[/FONT]c * c else k [FONT="]←[/FONT]k – 1 b [FONT="]←[/FONT]b * c end if end while return b Problem 3: Since k = n, I will assumed that everything within the while loop will again run in O(n) time, based on what you said before .. The basic operation then would be the b <- b*c, correct? But if that's the case, how would you go about determining how many times that process is run? The if/else statement is what confuses me on this one. Since the b <-b*c is dependent on the outcome of the if/else, how would I determine the runtime of that function? Perhaps I should research this whole Big Oh thing a bit further?