Tagged Questions
7
votes
2answers
97 views
Efficient computation of $\sum_{k=1}^n \lfloor \frac{n}{k}\rfloor$
I realize there is probably not a closed form, but is there an efficient way to calculate the following expression?
$$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor$$
I've noticed $$\sum_{k=1}^n ...
1
vote
0answers
20 views
simple formula to distribute inputs
I need a simple formula to do some math for my inputs to generate max number of fixed values ..
Below i wrote a simple logic for the math
lets say we have an object that will cost fixed numbers of 4 ...
2
votes
1answer
239 views
Trouble finding closed-form solution to summation
I have this question on my assignment for a computer science course (analysis of algorithms), so any help would be appreciated, but I am not looking for the answer itself.
I am trying to find the ...
0
votes
1answer
57 views
Is this formula for the number of nodes for a complete tree or a full and complete tree?
In a lecture it was said that "How many nodes are there in a complete k-ary tree with height h?" and this was the answer:
$$ \sum^{h}_{i = 0}k^i $$
where h is the height and k is the max number of ...
0
votes
1answer
61 views
Why is the upper bound of this statement always incremented by 1?
Why is "for j = 1 to n" translate to this? Why is the upper bound always incremented by 1?
$$\sum_{j=1}^{n+1}1 $$
Why isn't it
$$\sum_{j=1}^n1 $$
"for j = 1 to n" is written in pseudo code btw ...
0
votes
1answer
87 views
Is this why this summation is equivalent to this Theta notation?
So I'm not sure if I misunderstood the lesson or not.
$$T(n) =\sum_{j=2}^{n}\Theta(j) = \Theta(n^2) $$
Are these equivalent because:
$$ \sum_{j=2}^{n}\Theta(j) = \frac{n(n-1)}2 - \frac{1(1 - 1)}{2} = ...
1
vote
4answers
99 views
A puzzle related to loops.
For a given input $N$, how many times does the enclosed statement executes?
for $i$ in $1\ldots N$ loop
$\quad$for $j$ in $1\ldots i$ loop
$\quad$$\quad$for $k$ in $j\ldots i$ loop
...
