Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

#1
March 25th, 2003, 10:45 PM
 Deek
Junior Member

Join Date: Mar 2003
Posts: 1
Time spent in forums: < 1 sec
Reputation Power: 0
really basic question

I am starting analysis of algorithms for a class and I am having trouble with the basics, could someone help me work through this simple problem. Im not asking do it for me but I am not sure where to start. I read my prof book(which the problem is out of) but its explanations are too hard for me to understand.

prove or disprove each of the following:

f ( n ) = O(( f ( n ))^2)

if the statement is true prove it if false show how my example demonstrates it's false.

#2
March 26th, 2003, 02:26 AM
 riv
Contributing User

Join Date: May 2001
Posts: 465
Time spent in forums: 3 h 46 m 15 sec
Reputation Power: 13
Quote:
 f ( n ) = O(( f ( n ))^2)

To me it looks like algebra, just respect the basic rules of precedence: PEMDAS. Sounds hard to be true but then again, who is O?

BTW, what language is that?
__________________
Words must be weighed, not counted.

#3
March 26th, 2003, 05:11 AM
 tony825
Contributing User

Join Date: Jan 2003
Location: Greece
Posts: 63
Time spent in forums: < 1 sec
Reputation Power: 11
well it is 100% algorithms (comlexity, i think its called) but the question is what the f(n) is.

I mean the very same n ( an array[n] for example) has an different complexity {O[f(n)]} for a different algorithm f.

expl. the bublesort is n^2 and the quicksort is an O(n).

but just F( )..... it doent say a thing to me soory, if you could be more specific.
__________________
No sign

#4
March 26th, 2003, 09:59 PM
 infamous41md
not a fan of fascism (n00b)

Join Date: Feb 2003
Location: ct
Posts: 2,756
Time spent in forums: 2 Days 11 h 4 m 29 sec
Reputation Power: 94
that is bigO notation, referring to the asymptotic complexity of the algorithm. if i remember correctly, bigO is the worst case scenario, or upper bounds, of how an algorithm will perform. basically, the performance of an algorithm(f(n)) will never be worse than its bigO. that example is not true. one way to prove would be to take the function: n^2 + 2n + 50
the bigO of that is n^2, which is clearly not = to (n^2 + 2n + 50)^2 ... how did i get this? this stuff should be in ur book, and its rather hard to explain over a computer, but i can tell u this: with simple quadratic functions, the term with the highest power in it is almost always the bigO. This is b/c with extremely large values of n, that is the term that will grow at the highest rate.

#5
March 27th, 2003, 03:16 AM
 yassoor
Contributing User

Join Date: Feb 2003
Posts: 60
Time spent in forums: < 1 sec
Reputation Power: 11

Quote:
 Formal Definition: f(n) = O(g(n)) means there are positive constants c and k, such that 0 <= f(n) <= cg(n) for all n <= k. The values of c and k must be fixed for the function f and must not depend on n.

This formal definition is what you should be looking at to answer your question.

notice the difference between wour prof's question and the definition

The prof replaced g(n) by f(n)^2

so the real question is
Can this hold for all times
0 <= f(n) <= c( f(n)^2 ) for all n <= k.

is g(n) "the complixity of a function" always < (f(n)^2) ?
could it ever be possible that the big O complixity of a function be greater than f(n)^2 ?

I hope I have put you in the right direction, without answering the question for you.
__________________
I hope this is of any help to anyone.

Yassoor
http://www.WebsitesCreation.ca

#6
April 16th, 2003, 08:38 AM
 lazy_yogi
Contributing User

Join Date: Mar 2003
Posts: 325
Time spent in forums: 7 h 58 m 36 sec
Reputation Power: 11
just disprove by example

let f(n) = n^2 + 1

then [ f(n) ]^2 = n^4 + 2*(n^2) + 1

then O( [ f(n) ]^2 ) is n^4

and clearly n^2 + 1 != n^4

hence
f ( n ) != O(( f ( n ))^2)

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > really basic question