# Algorithm Analysis?

Discussion in 'OT Technology' started by hdot, Oct 14, 2008.

1. ### hdotNew Member

Joined:
Jan 25, 2007
Messages:
10,758
0
Location:
Texas
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..

2. ### CodeXGuest

Do you have a graphing calculator or mathmatica?

Graph n^2 against 10n*logn, find the point that they cross

3. ### hdotNew Member

Joined:
Jan 25, 2007
Messages:
10,758
0
Location:
Texas
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.

4. ### euphoricWho else here has some pants?Moderator

Joined:
May 22, 2002
Messages:
32,390
1
Location:
Austin, Texas
i wish my algorithims class was that easy

5. ### hdotNew Member

Joined:
Jan 25, 2007
Messages:
10,758
0
Location:
Texas

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

6. ### quzerNew Member

Joined:
Nov 9, 2003
Messages:
206
0
this is like calc 1 stuff lol
all you gotta do is solve this equation:

8n log(n) = 2n^2

7. ### hdotNew Member

Joined:
Jan 25, 2007
Messages:
10,758
0
Location:
Texas
Wow .. I should be punched in the face.

Thanks bro.

8. ### quzerNew Member

Joined:
Nov 9, 2003
Messages:
206
0
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

9. ### hdotNew Member

Joined:
Jan 25, 2007
Messages:
10,758
0
Location:
Texas
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=&quot]Foo[/FONT](a, n):
Input: two integers, a and n
Output: a^n
k [FONT=&quot]← [/FONT]0
b [FONT=&quot]←[/FONT] 1
while k < n do
k [FONT=&quot]←[/FONT]k + 1
b [FONT=&quot]←[/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..

10. ### Limp_BrisketNew Member

Joined:
Jan 2, 2006
Messages:
48,376
0
Location:
Utah
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

11. ### hdotNew Member

Joined:
Jan 25, 2007
Messages:
10,758
0
Location:
Texas
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=&quot]Bar [/FONT](a, n):
[FONT=&quot]Input[/FONT][FONT=&quot]: two integers, a and n[/FONT]
[FONT=&quot]Output: ?[/FONT]
[FONT=&quot]k ← n [/FONT]
[FONT=&quot]b ← 1[/FONT]
[FONT=&quot]c ← a[/FONT]
[FONT=&quot]while k > 0 do[/FONT]
[FONT=&quot]if k mod 2 = 0 then[/FONT]
k [FONT=&quot]←[/FONT]k / 2
c [FONT=&quot]←[/FONT]c * c
else
k [FONT=&quot]←[/FONT]k – 1
b [FONT=&quot]←[/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?