Trying to do Big O analysis- What is the average case for this program?. O(n/2(n/2)) = O(n^2) ?..

```
/* Returns the largest integer in the array */
int CompareToAll(int array[], int n)
{
int i, j;
bool isMax;/* Make sure that there is at least one element in the array.*/
if (n <= 0) return -1;
for (i = n-1; i > 0; i--)
{
isMax = true;
for (j = 0; j < n; j++) {
/* See if any value is greater.*/
if (array[j] > array[i]){
isMax = false; /* array[i] is not the largest value. */
break;
}
} /* If isMax is true, no larger valueexists; array[i] is max. */
if (isMax)
break;
}
return array[i];
}
```

Thank you

Yes, it's O(n^{2}) on average, assuming that the elements are randomly chosen. In the worst case you compare every element with every other element.

This algorithm is not optimal. It is possible to find the maximum element in an array using simple O(n) algorithm: iterate over the array once while keeping track of the largest element seen so far.

Similar Questions

I have a problem with the Big O: for i:=1 to n do for j:=1 to i*i do begin k:=1; m:=n; while m>=k do begin k:=k*3; m:=m/2 end end Teacher gave the answer - n*n*n*log(n). However, I can't get there

I need to convert two integers into two arrays of digits, so for example 544 would become arr[0] = 5, arr[1] = 4, arr[2] = 4. I have found some algorithms doing this, but they create new array, and r

I believe there's a way to find the kth largest element in an unsorted array of length n in O(n). Or perhaps it's expected O(n) or something. How can we do this?

The O(K * logK) algorithm for finding the largest K numbers in a max heap of size N is well known. I heard about that there is an O(K) algorithm for solving this problem. I do not find the literature

I want to implement at least two different solutions to find N-th largest element with O(N*log(N)) average time complexity in Big-O notation, where N is the number of elements in the list ? which sea

Next in my series of Big O questions that I can't find the answer to Take the following example for(int i = 0; i < someNumber; i++) { for(int j = i; j < someNumber; j++) { DoSomething(); } } Wo

I've been having some problems trying to grasp the concept of big O notation. So, by definition big O is as follows, T(n) ∈ O(G(n)) if T(n) <= G(n) * C. Since the the constant C can be any integ

For the below function, I did But I must have did wrong ... answer should be O(log n). I am terrible at Big O ... havent fully understood master theorem which is not taught in school yet. They tau

I am trying to get the correct Big-O of the following code snippet: s = 0 for x in seq: for y in seq: s += x*y for z in seq: for w in seq: s += x-w According to the book I got this example from (Pyth

Are there some possibility to complete a static code Analysis of C code with a minGW? I have read, that there is a possibility to do it with the help of mygcc. But is it possible to do it with MinGW?

Consider the function F: 2^(3*n) + n^2 Can the function A: 2^(3*n) be used as a Big Theta, Omega or O as a characterisation of F? Why? I'm revising the concepts of Big Omega, Big Theta and Big O and I

$scrname is my array. It contains integers and '-' if ('$scrname[2] != '-') { echo integer; } it not working Also I tried this: if (is_numeric ('$scrname[9]')) { echo integer; } This too not wor

I am doing the exercise of Skiena's book on algorithms and I am stuck in this question: I need to calculate the big O of the following algorithm: function mystery() r=0 for i=1 to n-1 do for j=i+1 to

The title above sums up my question, to clarify things an example is: array[0] = 1 array[1] = 3 array[2] = 7 // largest array[3] = 5 so the result I would like is 2, since it contains the largest ele

I need a random integer between 0 and an integer with over 1000 decimal places. Working with integers this large is easy with: big-integer (NPM), but there is no random method, and Math.random() does

Possible Duplicate: are there any O(1/n) algorithms? Is it ever possible for your code to be Big O less than O(1)?

Given an unsorted integer array and 2 numbers i and j such that 0 <= i <= j <= C(a constant say MAX_INTEGER) what kind of pre-processing can be performed on it so that you will be able to fin

I am attempting to calculate the Big-O of the following algorithm but I am confused and require some assistance: Algorithm 1. DFS(G,n) Input: G- the graph n- the current node 1) Visit(n) 2) Mark(n) 3)

My question arises from the post Plain English Explanation of Big O. I don't know the exact meaning for logarithmic complexity. I know that I can make a regression between the time and the number of

So I have this problem to do and I am not really sure where to start: Using the definition of Big-O, prove the following: T(n) = 2n + 3 ∈ O(n) T(n) = 5n + 1 ∈ O(n2) T(n) = 4n2 + 2n + 3 ∈ O(n2) if an

I asked a question about Big-Oh / Big-Theta but they acquired constants in them It is Big Oh and does not have any visible constants in it so I don't know where to start off with this since it is a s

for (int j=0,k=0; j<n; j++) for (double m=1; m<n; m*=2) k++; I think it's O(n^2) but I'm not certain. I'm working on a practice problem and I have the following choices: O(n^2) O(2^n) O(n!) O(

What's the big-O complexity for the following loop: for each vertex u ∈ C do for each vertex v ∈ C and v > u do What I'm doing here is imagine the following set {1,2,3,4} the loop executes a funct

I'm struggling with understanding Big O and I'm unable to quite comprehend the multiple ways that I read, and watch, that are used to find the Big O of a function. It seems that every video or post ha

Is O(5n) = 5*O(n) ? From what I understand , O(5n) == O(n). Thus they are not equal? Please correct me if I am wrong.

for(int i=N; i>0; i=i/2) irrelevant statement; I am asked to find the complexity class and I am unsure of whether I am supposed to use Big-Omega notation or Big-O? But I am assuming that it is O(N

Hello I am writing this program, and I am trying to figure out how to compare two items in an array to find the largest item. public static <T extends Comparable< ? super T>> T getLargest(

What is the Big-O for SQL select, for a table with n rows and for which I want to return m result? And What is the Big-O for an Update, or delete, or Create operation? I am talking about mysql and sql

Maybe this is a stupid question, but I am trying to find the math rule to prove that: O(n^2.3) is less efficient than O(n^2logn)

I am learning algorithm analysis. While doing the theory I across many big-O proofs. I was able to solve them but I need help with omega which is the oposite of big-O? Is 22n = O(2n)? --->My answer

I'm having a problem coming up with an algorithm for a big integer class in C++. My initial idea was using arrays/lists, but it's very inefficient. I then discovered about things like the following cl

What is the Big-O complexity for widespread algorithms of the basic arithmetic operations like multiplication, square root, logarithm, scalar and matrix product? Are there exotic algorithms which are

for example, say n = Integer.MAX_VALUE or 2^123 then O(log(n)) = 32 and 123 so a small integer. isn't it O(1) ? what is the difference ? I think, the reason is O(1) is constant but O(log(n)) not. Any

Possible Duplicate: How might I find the largest number contained in a JavaScript array? I am having trouble getting this code to work I have been at it for a while trying to figure it out. When I l

I'm trying to figure out where O(sqrt(n)) and O(n2 log n) fit in this growth hierarchy listed below. This chapter is so confusing and i'm lost on how to figure this out. Any suggestions would be much

How can I represent the complexity of std::find_end algorithm as Big-O notation? The complexity of std::find_end is defined as follows: At most (last2 - first2) * (last1 - first1 - (last2 - first2) +

I am trying to understand what exactly Big O notation is. I understand it in the literal and practical sense by going through the answers of similar questions in SO. But what the answers don't explain

I'm reading this Big O article (and some other book references) trying to figure out what changes affect my algorithm. so given the following O(N^2) code: bool ContainsDuplicates(String[] strings) {

I have an unsorted array with n*n order. How to get the largest element from each row with complexity O(n logn).

How would we be able to guess the big-O speed of a program given that we have the values of n and corresponding running times? Mind you, I do not come from a CS background and I have done some reading

I was looking for a good resource on Asymptotic Analysis. Now I am not looking for a book that tells me the runtime of this algorithm is O(N). I want to find a book that teaches me how to actually a

This question already has an answer here: How to find the kth largest element in an unsorted array of length n in O(n)? 21 answers I'm trying to find the N-th largest element in a large 2-D arr

How can I convert a string of numeric values 20,30,40,42; into {20,20,40,42} integer array in Objective C.

I am writing a simple big integer library for exercise. I would like to use it in a simple implementation of RSA. I have read all the previous threads but I have not found an answer to my question. I

Suppose f(n) is runtime of algorithm. According to function definition of O(n), if f(n)<=c*g(n) then f(n)=O(g(n)) where n0<=n. What is the range of values constant c can take?

I'm solving some recurrence relation problems for Big O and so far up till this point have only encountered recurrence relations that involved this form: T(n) = a*T(n/b) + f(n) For the above, it's qu

Possible Duplicate: What’s the complexity of for i: for o = i+1 I have done the following sorting algorithm for arrays of length 5: int myarray[5] = {2,4,3,5,1}; int i; for (i = 0; i < 5; i++) {

I'm searching for the Big-O complexity of PageRank-Aglorithm. I hardly could found anything, I just found O(n+m) ( n - number of nodes, m - number of arcs/edges) but I didn't believe this complexity b

I've tried to come up with the Big O Running time of the following data structures. Are they Correct? Inserting n integers into an initially empty AVL Tree (best case) O(log n) Inserting n integers i

I was having problem with the following question Consider the following nested loop construct. Categorize its efficiency in terms of the variable n using big-o notation. Suppose the statements repre