# Все вопросы: [big-o]

91 вопросов

похожие теги: big-ipmach-olittle-obig-theta
5ответов
425 просмотров

### O Notation Help

I am getting stuck with the class work we got this week and its a subject i really want to learn so for once i thought i would do the additional reading!!!! The method is provided for us and i am just writign some test cases. This is where my knowledge gets a little hazy. If the time increases t...

7ответов
16761 просмотров

### A homework about growth rate of function

Please order the function belows by growth rate n ^ 1.5 n ^ 0.5 + log n n log ^ 2 n n log ( n ^ 2 ) n log log n n ^ 2 + log n n log n n ps: Ordering by growth rate means, as n gets larger and larger, which function will eventually be higher in value than the others. ps2. I have ordered most o...

3ответов
241 просмотров

### Complexity of a given function

When I analyzed the complexity of the code segment below, I found that it is O(n/2). But while searching the internet I discovered that it is probably O(n). I'd like to know who's correct. void function(int n) { int i = 1, k = 100; while (i &lt; n) { k++; i += 2; } }

7ответов
38312 просмотров

### Is Big O(logn) log base e?

For binary search tree type of data structures, I see the Big O notation is typically noted as O(logn). With a lowercase 'l' in log, does this imply log base e (n) as described by the natural logarithm? Sorry for the simple question but I've always had trouble distinguishing between the differ...

31ответов
19566 просмотров

### O(nlogn) Algorithm - Find three evenly spaced ones within binary string

I had this question on an Algorithms test yesterday, and I can't figure out the answer. It is driving me absolutely crazy, because it was worth about 40 points. I figure that most of the class didn't solve it correctly, because I haven't come up with a solution in the past 24 hours. Given a ar...

3ответов
779 просмотров

### Asymptotic analysis of code fragment

I need to find the big O running time of the following fragment: sum =0; for (int i=1; i&lt;n; i++) { for (int j=1; j&lt; n/i; j++) { sum = sum +j; } } I know the outer loop is O(n) but I am having a problem analyzing the inner loop. I think it's O(log n).

2ответов
193 просмотров

### Program Runtime HW Problem

An algo takes .5 ms seconds for an input size of 100, how long will it take to run if the input size is 500 and the program is O(n lg(n))? My book says that when the input size doubles, n lg(n), takes "slightly more than twice as long". That isn't really helping me much. The way I've ...

23ответов
15445 просмотров

### O(log N) == O(1) - Why not?

Whenever I consider algorithms/data structures I tend to replace the log(N) parts by constants. Oh, I know log(N) diverges - but does it matter in real world applications? log(infinity) &lt;100 for all practical purposes. I am really curious for real world examples where this doesn't hold....

1ответов
1796 просмотров

### Calculating a Theta (Tight Bound) Estimation

I was just wondering if someone could explain this a little to me. I want to know how to calculate an estimate for a Theta function using the integrals or the truncate-and-bound method. For Example how would you calculate: ∑i=1..n i⋅sqrt(i)+1

6ответов
4468 просмотров

### Efficiency of Sort Algorithms

I am studying up for a pretty important interview tomorrow and there is one thing that I have a great deal of trouble with: Sorting algorithms and BigO efficiencies. What number is important to know? The best, worst, or average efficiency?

2ответов
311 просмотров

### What is the proper method to go about finding the order of growth for this function?

2^n + 6n^2 + 3n I guess it's just O(2^n), using the highest order term, but what is the formal approach to go about proving this?

1ответов
420 просмотров

### Relative asymptotic behavior of these functions

I have 3 functions: f(n)=2n, g(n)=n! and h(n)=nlog(n) (log(n) is base 2). Comparing f(n) and g(n): The factorial function, g(n) can be approximated as O(nn) (poor upper bound). Considering this, Is g(n)=Ω(f(n)) ? How would I compare g(n) and h(n), and f(n) and h(n)?

5ответов
17511 просмотров

### Can someone explain how Big-Oh works with Summations?

I know this isn't strictly a programming question, but it is a computer science question so I'm hoping someone can help me. I've been working on my Algorithms homework and figuring out the Big-Oh, Big-Omega, Theta, etc, of several algorithms. I'm proving them by finding their C and N0 values an...

5ответов
25655 просмотров

### What is an easy way for finding C and N when proving the Big-Oh of an Algorithm?

I'm starting to learn about Big-Oh notation. What is an easy way for finding C and N0 for a given function? Say, for example: (n+1)5, or n5+5n4+10n2+5n+1 I know the formal definition for Big-Oh is: Let f(n) and g(n) be functions mapping nonnegative integers to real numbers. We say t...

4ответов
249599 просмотров

### Difference between Big-O and Little-O Notation

What is the difference between Big-O notation O(n) and Little-O notation o(n)?

3ответов
13839 просмотров

### What is the Big-O for SQL select?

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 sqlite in general.

12ответов
10339 просмотров

### Time complexity O() of isPalindrome()

I have this method, isPalindrome(), and I am trying to find the time complexity of it, and also rewrite the code more efficiently. boolean isPalindrome(String s) { boolean bP = true; for(int i=0; i&lt;s.length(); i++) { if(s.charAt(i) != s.charAt(s.length()-i-1)) { bP...

2ответов
3411 просмотров

### How Prim's algorithm time complexity is ElogV using Priority Q?

Pseudo code which I used: for all V vertices: visited[n]=0 pick any vertex r from graph and set visited[r]=1 For all edges e incident to r PQ.insert() while(PQ is not empty)//line 1 f=PQ.min()//f(r,s) is such that visited[s]=0 for all edges e(s,t) incident to s//line 2 if(visited...

8ответов
1806 просмотров

### What is O value for naive random selection from finite set?

This question on getting random values from a finite set got me thinking... It's fairly common for people to want to retrieve X unique values from a set of Y values. For example, I may want to deal a hand from a deck of cards. I want 5 cards, and I want them to all be unique. Now, I can do ...

3ответов
3312 просмотров

### Is it ever possible to have Big O less than O(1)?

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

14ответов
2252 просмотров

### Is this code O(N) or O(1)

vector&lt;int&gt;::iterator it; vector&lt;int&gt; p; p.push_back(4); p.push_back(5); p.push_back(6); p.push_back(7); it = p.begin() + 2; cout &lt;&lt; it &lt;&lt; endl; Is this O(N) or O(1)? And why?

7ответов
2161 просмотров

### Big O Notation for an Algorithm

I can't solve a problem; can someone help me? What is the Big O notation for the below statement:- for (int i=2;i&lt;=n;i=i*4) sum++;

11ответов
4980 просмотров

### Do you use Big-O complexity evaluation in the 'real world'?

Recently in an interview I was asked several questions related to the Big-O of various algorithms that came up in the course of the technical questions. I don't think I did very well on this... In the ten years since I took programming courses where we were asked to calculate the Big-O of algori...

3ответов
1562 просмотров

### Some Questions on Complexity

1) Reorder the following efficiency from smallest to largest: 2^n, n!, n^5, 10000, nlog2(n) My Ans-&gt; 10000 Correct ? 2) Efficiency of an algo. is n^3, if a step in this algo. takes 1 nanosec. (10^-9 sec.). How long does it take the algo. to process an input of size 1000? I don'...

5ответов
1394 просмотров

### Regex implementation that can handle machine-generated regex's: *non-backtracking*, O(n)?

Edit 2: For a practical demonstration of why this remains important, look no further than stackoverflow's own regex-caused outage today (2016-07-20)! Edit: This question has considerably evolved since I first asked it. See below for two fast+compatible, but not completely fully featured impleme...

3ответов
3772 просмотров

### how to find the time complexity using step count

sum(array,n) { tsum=0; for(i=0;i&lt;n;i++) tsum=tsum+array[i]; return tsum; }

6ответов
864 просмотров

### Is there a O(nlog(n)) algorithm for inverting a simply linked list?

In comments to this answer an idea is brought up that inverting a simply linked list could only be done in O(nlog(n)), not O(n) time. This is definitely wrong – an O(n) inversion is not a problem - just traverse the list and change pointers as you go. Three temporary pointers are required - that...

5ответов
323 просмотров

### Большой O: общая производительность ʻIterateArray` равна O (n) или O (n log n)?

Если у меня есть следующий код: IterateArray(object[] array) { for(int i=0; i&lt;array.length; i++) { Dosomething(array[i]); } } а временная производительность метода Dosomething(object) равна O (log n), это общая производительность IterateArray O (n) или O (n log n)?

7ответов
21692 просмотров

### Является ли System.currentTimeMillis () лучшим показателем производительности времени в Java?

Является ли System.currentTimeMillis () лучшим измерителем производительности времени в Java? Есть ли какие-то ошибки при использовании этого для сравнения времени до того, как действие было предпринято, со временем после того, как действие было предпринято? Есть ли лучшая альтернатива?

11ответов
1590 просмотров

### Вопрос анализа алгоритма

ПРИМЕЧАНИЕ. Я новичок в анализе алгоритмов, поэтому не принимайте мои утверждения как абсолютную истину, все (или все), что я утверждаю, может быть неправильным. Привет, я читал об анализе алгоритмов и "большой нотации" и кое-что озадачил. Предположим, вас попросили напечатать все перест...