473,396 Members | 1,714 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,396 software developers and data experts.

express the function in Ω-notation

i'm learning algorithm analysis, about the different notations, and in class we wrote an example:

f(n) = 1/2*n^2 + 3n,

and wrote it using O-notation, Ω-notation and Θ-notation:

T(n) = Ω(n)
T(n) = O(n^2)
T(n) = Θ(n^2)

now i'm reading the book, where it says f(n) = Θ(g(n)) is true if and only if both f(n) = O(g(n)) and f(n) = Ω(g(n)) are correct.

in the example we wrote, it says T(n) = Θ(n^2) (which i do agree with) which means both T(n) = O(n^2) and T(n) = Ω(n^2) should hold. but we wrote T(n) = Ω(n). i think that's incorrect? (we wrote that because of the term 3n which means that at least 3n operations are done)

i think it should be T(n) = Ω(n^2) instead of Ω(n)

please correct me if i'm wrong. thanks in advance
Mar 4 '17 #1
0 2883

Sign in to post your reply or Sign up for a free account.

Similar topics

699
by: mike420 | last post by:
I think everyone who used Python will agree that its syntax is the best thing going for it. It is very readable and easy for everyone to learn. But, Python does not a have very good macro...
9
by: Derek Hart | last post by:
I wish to execute code from a string. The string will have a function name, which will return a string: Dim a as string a = "MyFunctionName(param1, param2)" I have seen a ton of people...
7
by: MLH | last post by:
Is the following remotely correct? =DDE("C:\Program Files\Program Files\Outlook Express\OEmig50","Attachment","Name") I'm not sure that OEmig50.exe is the executable for OE. Anybody know? ...
11
by: Ken Varn | last post by:
I want to be able to determine my current line, file, and function in my C# application. I know that C++ has the __LINE__, __FUNCTION__, and __FILE___ macros for getting this, but I cannot find a...
1
by: sck10 | last post by:
Hello I am using Visual Web Developer 2005 Express. Whenever I use the "copy web site" function, it creates a "publishform" button on my task bar that doesn't go away. So if I publish 3...
26
by: Tom Becker | last post by:
Is there a way, from Access, to programmatically click the Send and Receive button in Outlook?
4
by: mecej4 | last post by:
DB2 Express C (Fixpack 10, WR21362_15462) seems to be lacking some of the OLAP functions available in other editions, such as ROW_NUMBER, RANK and DENSE_RANK, but does provide sum(..) over...
10
by: Daniel | last post by:
In Microsoft Access I can write a query that includes the criteria: Between Date()-7 And Date() to retrieve the records from a table that fall within the last week. I'm trying to write a...
4
by: Tony Lownds | last post by:
(Note: PEPs in the 3xxx number range are intended for Python 3000) PEP: 3107 Title: Function Annotations Version: $Revision: 53169 $ Last-Modified: $Date: 2006-12-27 20:59:16 -0800 (Wed, 27 Dec...
9
by: HC | last post by:
Hello, all, I started out thinking my problems were elsewhere but as I have worked through this I have isolated my problem, currently, as a difference between MSDE and SQL Express 2005 (I'll just...
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
0
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
0
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
0
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers,...
0
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
0
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.