Linked Questions

1
vote
0answers
65 views

how to interpret O(1) + O(2) + ... + O(n)? [duplicate]

in the book "Introduction to algorithms"(CLRS) page 49 it says: "The number of anonymous functions in an expression is understood to be equal to the number of times the asymptotic notation ...
92
votes
11answers
23k views

Solving or approximating recurrence relations for sequences of numbers

In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...
96
votes
3answers
31k views

How does one know which notation of time complexity analysis to use?

In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are ...
6
votes
3answers
22k views

What is the asymptotic runtime of this nested loop? [duplicate]

I am trying to analyse the runtime of this algorithm: for(i=1; i < n; i++){ for(j=1; j <= i; j++){ statement1; } } Expanding the ...
14
votes
3answers
870 views

What goes wrong with sums of Landau terms?

I wrote $\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$ but my friend says this is wrong. From the TCS cheat sheet I know that the sum is also ...
7
votes
2answers
2k views

Is $n$ times $O(1)$ equivalent to $O(n)$? [duplicate]

I am having a hard time figuring out if $$\sum^n_{i=0} O(1) =O(n)\,.$$ I think it doesn't but I am unable to find a convincing explanation for that, does anyone have an intuitive yet mathematical ...
8
votes
2answers
288 views

Why doesn't $O(1)+O(2)+\cdots+O(n)$ have an interpretation?

In CLRS (on pages 49-50), what is the meaning of the following statement: $\Sigma_{i=1}^{n} O(i)$ is only a single anonymous function (of $i$), but is not the same as $O(1)+O(2)+\cdots+O(n)$, which ...
0
votes
1answer
820 views

Why is Heapsort in O(n log n) if not all n operations take time log n?

let's consider that we already have constructed heap array. so from this, when we do heap sort, the number of elements that have to be sorted decreased. I mean heap decrease.(which also means heap ...
3
votes
1answer
445 views

Asymptotic analysis of a summation

I was calculating the time complexity of one of the phases of my proposed algorithm, but unfortunately, I faced a problem about solving that and providing an understandable running-time. This phase of ...
2
votes
1answer
124 views

How does O transform this sum like that?

I'm in the process of self-studying the CLRS book. My mathematical background is poor so I'm trying to learn the maths as I go along too. I don't understand the math in CLRS section 6.4 where they go ...
1
vote
0answers
107 views

Why does $\sum\limits_{i=0}^{\lg(n)-1} \theta(\frac{n}{2^i}) = \theta(n\lg(n))$?

I'm reading a proof on the time complexity of MergeSort which makes this statement without any justification. I've tried to show it myself but I'm not getting far; these are my steps so far. $\sum\...
0
votes
2answers
116 views

How to show working for summing of Big O notation

The equation below is intuitively correct, but how do you show that this is actually the case? What is the working out needed? $$\sum_{i=1}^{n-1}O(\lg n)=O(n\lg n)$$