I'm confused about how to do big-O analysis for the following problem -

find an element from an array of integers. ( an example problem)

my solution

- sort the array using bubble sort ( n^2 )
- binary search on the array for a given element (logn)

now the big-O for this is n^2 or n^2 + logn ? Should we only consider the higher term ?

The way you did it, it would be O(n^2), since for large n, n^2 >>> logn

Only the higher order term. The complexity is always the complexity of the highest term.

Big-O for a *problem* is that of the *best* algorithm that exists for a problem. That for an *algorithm* made of two steps (like yours) is indeed the highest of the two, because e.g.

```
O(n^2) == O(n^2 + log n)
```

However, you can't say that `O(n^2)`

is the correct `O`

for your sample *problem* without proving that no better algorithm exists (which is of course not the case in the example;-).

To put the analysis, well, more-practically (if you prefer, crudely) than Alex did, the added **log n** doesn't have an appreciable effect on the outcome. Consider analyzing this in a real-world system with one million inputs, each of which takes one millisecond to sort, and one millisecond to search (it's a highly-hypothetical example). Given O(n^2), the sort takes over thirty years. The search takes an additional 0.014 seconds. Which part do you care about improving? :)

Now, you'll see algorithms which clock in at **O(n^2 x logn)**. The effect of multiplying **n^2** by **log n** makes **log n** significant - in our example, it sees our thirty years and raises us four centuries.

Similar Questions

I am using perf tool to analyze sort utility . I gave following command. perf stat -x, ../bin/sort data >/dev/null 2>perf_data I want to redirect the output of sort to /dev/null and output of p

How do I write a code analysis tool for vs2008 to prevent a specific framework call, such as GC.WaitForFullGCComplete() or Application.DoEvents() I tried overriding the VisitMethodCall in my custom ru

This question already has an answer here: Nested loops into mathematical model to count number of operations 4 answers I'm doing some self study for algorithms and I can't figure out why the if

I'm trying to use sonar for static analysis on a c++ code. I've installed sonar and configured my project (it appears on the localhost sonar page, but i do not see any code violation for the respectiv

Ok, these are all pretty simple methods, and there are a few of them, so I didnt want to just create multiple questions when they are all the same thing. BigO is my weakness. I just cant figure out ho

How are algorithms analyzed? What makes quicksort have an O(n^2) worst-case performance while merge sort has an O(n log(n)) worst-case performance?

I am sure this is as simple as a question can get but I have been stumped on it so figured that I would ask in hope of a quick response. Using an OLEDB connection I want to do a select statement but f

I am having issues fully understanding how to prove some of the following statements. For instance I have a statement: n^2logn = O(n^2). Correct me if I am wrong, but this states that n^2 is bigO of n

i need to make this analysis using mapReduce and/or aggregate: DBCollection coll = db.getCollection(documents); DBCursor cursor = coll.find(); Map<String,Integer> map = new HashMap<String,I

I'm trying to learn ggplot2 to apply it to my own data, but have encountered a problem when trying to reproduce a plot from the book 'Elegant Graphics for Data Analysis' by Hadley Wickham (Fig 4.10 (r

NCover has an attribute IgnoreFromCoverage that allows for code to be marked for exclusion during code coverage analysis. Is there a way to do this with the VSTS Code Coverage Tools? Obvious uses for

I'm wondering about an algorithm solving the following (efficiently): A 2D matrix of numbers [1..9] which need to align in horizontal lines from top (1) to bottom (9), but only through flipping either

I recently figured out how to do localization in MVC using resource files containing strings. Kind of cool that MVC automatically picks the resource file for the visitor's language. I like that! Howev

I am recently working on a problem which I think is a fork of the set cover problem. However, the number of sets in my problem is as large as 2^n. And the approximate alogrithms I've found seem to be

I submitted another version of this question and a sample program before: How do I get consistent rendering when scaling a JTextPane? Recapitulating the problem: I would like to allow users to zoom in

Looking for free/opensource code or description of algorithms to code (simple) and decode (hard) the 2D barcode QR code. It doesn't seem like a trivial problem, but it's so popular in Japan that there

How do I visualize a break-even analysis with Flex's AreaChart? Mats

I just recently started learning about genetic algorithms and am now trying to implement them in 2D shape optimization in physics simulaiton. The simulation produces a single scalar for each shape. (I

Where can I find some good tutorials with examples with free data, on how to implement metaheuristics algorithms in R ? I am asking this because I found lots of resources on how to do it, however I am

Analysis of PSRS (Parallel sorting by regular sampling) In Computation part. Why Big-o of Sorting regular samples : O(p^2 log p^2) = O(p^2 log p) ? Thank you for answering.

I'm looking to have 2 buttons for forms that do 2 different actions when clicked shown next to each other This is best explained on the following link: http://jsfiddle.net/pfeHA/1/ The code involved i

How do I apply case analysis in Isabelle? I was looking for something similar to apply (induct x) (which is used for induction).

Can somebody explain to me how is the pred field in stl algorithms exactly used? Thank you

Sorry in advance if I'm not explaining this correctly. I want to know if there are algorithms to weight various factors in a decision process. I was reading programming collective intelligence and the

I would like to keep model binding when doing ajax calls from my view. I'm using jquery ajax to make the calls, and just as an example- this is my controller method I want to call from ajax: public Ac

for power analysis ,first time i try to generate .vcd but getting error.tell me how to remove it module dct_test; // Inputs reg [6:0] x0; reg [6:0] x1; reg [6:0] x2; reg [6:0] x3; // Outputs wire [9:0

I am attempting to prepare a presentation to explain the basics of algorithm analysis to my co-workers - some of them have never had a lecture on the subject before, but everyone has at least a few ye

Using jquery qTip2 for tooltips. I have a tooltip with a link in it. I want the tip to stay open if the user's mouse enters the tip (not the trigger). Can't seem to figure out how to do that in the do

Edit: I'm using Python 3 (some people asked). I think this is just a syntax question, but I want to be sure there's nothing I'm missing. Notice the syntax difference in how Foo and Bar are implemented

I have this query: select top(2) property_id_ref ,image_file ,property_name from property_master a inner join image_master b on a.property_id=b.property_id_ref inner join customer_master c on a.custom

I have just started learning and usingASP.NET MVC 2 and also getting more involved into unit testing my code. My question is broadly how to simulate a user log in by passing in credentials within my t

I've deployed a Node.js application using AWS Elastic Beanstalk. How do I view logs (like the output from console.logs) in real-time for the server? I'm able to SSH into the Linux instance, but am not

I'm a relative newcomer to cocoa & programming for the ipad. I've built an app that has a split view controller. In the detail view is a toolbar with a button on it. When the button is pressed, th

How can we classify various Algorithms? I have heard various names: Divide & Conquer Algorithms, Deterministic Algorithms, Probabilistic Algorithms, In-place Algorithms and so on. Do they form any

I have enabled code analysis for all the projects in a solution. To overcome various code analysis warnings the code contains numerous code suppression attributes (System.Diagnostics.CodeAnalysis.Supp

This question on Cyclomatic Complexity made me think more about static code analysis. Analyzing code complexity and consistency is occasionally useful, and I'd like to start doing it more. What tools

How i can do Technical Analysis indicator calculations like Average directional index, stochastic oscillators etc in SQL SERVER database by using T-SQL as doing in excel? If it possible, is it good fo

Supposer I've 4 varaibles (x, y, z, r) & 10 obs. I run the cluster analysis in R & get 2 clusters which are appropriate. Now I want to put these clusters in corresponds to the data. So the tab

1) x = 25; for (int i = 0; i < myArray.length; i++) { if (myArray[i] == x) System.out.println(found!); } I think this one is O(n). 2) for (int r = 0; r < 10000; r++) for (int c = 0; c <

How do we disable the Continuous Analysis option in Klocwork by default? I know how to disable it for the Eclipse plugin and for .sln files, which works fine, but this is an additional step that mus

How do I merge 2 NSSets in objective-c ? I can't find solution on google.

I have an AdjacencyList class and I want all graph algorithms to be seperated from it. Let's say all algorithms are functors and derive from GraphAlgorithm abstract base class. How do I make it work?

How do I plot the equivalent of contour (base R) with ggplot2? Below is an example with linear discriminant function analysis: require(MASS) iris.lda<-lda(Species ~ Sepal.Length + Sepal.Width + Pet

I'm reading Matrix decompositions and latent semantic indexing (Online edition © 2009 Cambridge UP) I'm trying to understand how you reduce the number of dimensions in a matrix. There's an example on

I am using the MERGE INTO statement to work with some tables, and I've a simple question. How can I make a Matched/Not Matched Statement do 2 things? For example, I have this and it works: MERGE INTO

while performing sentiment analysis, how can I make the machine understand that I'm referring apple (the iphone), instead of apple (the fruit)? Thanks for the advise !

I have a very simple code (simplified from the original code - so I know it's not a very clever code) that when I compile in Visual Studio 2010 with Code Analysis gives me warning CA1062: Validate arg

I have a fresh 64 bit SS 2008 R2 install on a new server running 64 bit Windows 7. (No previous versions of SS). BIDS is running on the same box as SS 2008 R2. I ran the Analysis Services tutorial, to

I have run ASIHTTPRequest successfully. I got it from the link, http://github.com/pokeb/asi-http-request/tarball/master. Since I just started to learn xCode, I am not sure how to get ASIHTTPRequest in

I have a separate landscape view of a clock i've made and I want this to cross dissolve in when the phone is rotated to landscape, and then cross dissolve back when it returns to portrait, but when I'