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

91 вопросов

похожие теги: big-ipmach-olittle-obig-theta
0
голосов
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...

3
голосов
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...

1
голосов
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 < n) { k++; i += 2; } }

96
голосов
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...

173
голосов
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...

4
голосов
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<n; i++) { for (int j=1; j< 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
голосов
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 ...

47
голосов
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) <100 for all practical purposes. I am really curious for real world examples where this doesn't hold....

1
голосов
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

4
голосов
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?

0
голосов
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?

0
голосов
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)?

9
голосов
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...

12
голосов
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...

340
голосов
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)?

22
голосов
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.

6
голосов
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<s.length(); i++) { if(s.charAt(i) != s.charAt(s.length()-i-1)) { bP...

4
голосов
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...

12
голосов
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 ...

0
голосов
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)?

0
голосов
14ответов
2252 просмотров

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

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

4
голосов
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<=n;i=i*4) sum++;

16
голосов
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...

0
голосов
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-> 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'...

16
голосов
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...

2
голосов
3ответов
3772 просмотров

how to find the time complexity using step count

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

2
голосов
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...

4
голосов
5ответов
323 просмотров

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

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

17
голосов
7ответов
21692 просмотров

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

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

4
голосов
11ответов
1590 просмотров

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

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