I came across this problem
for (int i = n; i > 1; i = i / 4) {
for (j = 0; j < n; j++) {
F()
}
}
and I need to find the closed form for how many times F() is called so I can get the big o of it. I'm pretty sure it is O(n*log(n)), but I want to find it using summations.
Right now I have $\sum_{i = n}^1 \sum_{j = 0}^n 1$, but that doesn't seem right at all since $i$ is being divided by 4 each iteration. I also noticed that if $n = 4^k$ then we can see how many times it runs at a certain points using $a_k = \frac{n}{4^k}$, but I'm not sure what to do with that.
Not really sure how to express in in a closed form because of that first loop, so any help would be appreciated.