渐近预期运行时间(Asymptotic Expected Running Time)

 我在渐近分析问题上遇到了一些麻烦。 该问题要求渐近最坏情况运行时间和函数的渐近预期运行时间。 Random（n）在1和n之间生成一个均匀分布的随机数（1到n之间的每个整数都是相同的。） 
 
Func2(A, n)
/* A is an array of integers */
1 s ← A[1];
2 k ← Random(n);
3 if (k < log2(n)) then
4    for i ← 1 to n do
5       j ← 1;
6       while (j < n) do
7          s ← s + A[i] ∗ A[j];
8          j ← 2 ∗ j;
9       end
10   end
11 end
12 return (s);
 
 我想知道第3行（if（k <log2（n））然后如何影响函数的预期运行时间。 我认为第4-10行在最坏情况下运行cn ^ 2时间，但我不确定如何根据if语句推导出预期的运行时间。 谢谢你的帮助！ 
 
 -Matt 

I'm having some trouble with an asymptotic analysis question. The problem asks for both the asymptotic worst case running time and the asymptotic expected running time of a function. Random(n) generates a random number between 1 and n with uniform distribution (every integer between 1 and n is equally likely.)
 
Func2(A, n)
/* A is an array of integers */
1 s ← A[1];
2 k ← Random(n);
3 if (k < log2(n)) then
4    for i ← 1 to n do
5       j ← 1;
6       while (j < n) do
7          s ← s + A[i] ∗ A[j];
8          j ← 2 ∗ j;
9       end
10   end
11 end
12 return (s);
 
I was wondering how line 3 (if (k < log2(n)) then) effects the expected running time of the function. I believe lines 4 - 10 run at worst case cn^2 time, but I am unsure how to derive the expected running time due to the if statement. Thanks for any help!
 
-Matt

原文：https://stackoverflow.com/questions/14689122