> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook-spring-2026/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook-spring-2026/12.-asymptotics-ii/12.4-for-loops-print-party.md). # 12.4 For Loops Print Party ## Print Party Example: Let's look at a more involved example next. Consider the following function, with similar nested for loops: ```java public static void printParty(int N) { for (int i = 1; i <= N; i = i * 2) { for (int j = 0; j < i; j += 1) { System.out.println("hello"); int ZUG = 1 + 1; } } } ``` The outer loop advances by *multiplying* `i` by 2 each time. The inner loop runs from 0 to the current value of `i`. The two operations inside the loop are both constant time, so let's approach this by asking **"how many times does this print out "hello" for a given value of N?"** Our visualization tool from above helped us see dup1's runtime, so let's use a similar approach here. We'll lay out the grid for the nested for loops, and then track the total number of print statements needed for a given N below. If N is 1, then `i` only reaches 1, and `j` is only 0, since 0 < 1. So there is only one print statement:

If N is 2, the next time through the loop `i` will be $$1\*2 = 2,$$ and `j` can reach 1. The total number of print statements will be 3 = 1 (from first loop) + 2 (from second loop).

Conceptual Check: What happens when N = 3?

After the second loop, $$i = 2 \* 2 = 4$$, which is greater than $$N$$, so the outer loop does not continue, and ends after `i = 2`, just like N = 2 did. N = 3 will have the same number of print statements as N = 2. The next change is at N=4, where there will be 4 prints when i = 4, 3 prints when i = 2, and 1 print when i = 1 (remember `i` never equals 3). So a total of 7.

We can keep filling out our diagram to get a fuller picture. Here it is up to N = 18:

What we see, if we add up all the counts at each stage of the loops, is that the number of print statements is: $$ C(N) = 1 + 2 + 4 + ... + N $$ (if N is a power of 2). Again, we can think of this in two ways. Since we're already on a graphical roll, let's start there. ### Method 1: Finding the Bound Visually If we graph the trajectory of 0.5 N (lower dashed line), and 4N (upper dashed line), and $$C(N)$$ itself (the red staircase line), we see that C(N) is fully bounded between those two dashed lines.

Therefore, the runtime (by definition) must also be linear: $$\theta(N)$$. ### Method 2: Finding the Bound Mathematically We can obtain the same result by solving our equation from above with the power of mathematics: $$ C(N) = 1 + 2 + 4 + ... + N = 2N - 1 $$ Again if N is a power of 2. For example, if $$N = 8$$ : $$ C(N) = 1 + 2 + 4 + 8 = 15 = 2\*8 - 1 $$ And by removing lesser terms and multiplicative constants, we know that $$2N - 1$$ is in the linear family, so the runtime is $$\theta(N)$$. We now get a more exact value to the red-staircase line plotted below, which is $$2N$$.

## Techniques: No Magic Shortcuts {% embed url="" %} It would be really nice if there were some magic way to look at an algorithm and just *know* its runtime. And it would be even nicer if all nested for loops have a runtime of $$N^2$$ . Unfortunately, they're not. And we know this because we just did two nested for loop examples above, each with *different* runtimes. In the end, there is **no shortcut** to doing runtime analysis. It requires careful thought. But there are a few useful techniques and things to know: * **Find exact sum** * **Write out examples** * **Draw pictures** We used each of these techniques above. Also used in the examples above are two important sums you'll see very often: * **Sum of First Natural Numbers**: $$1+2+3+...+Q=Q(Q+1)/2=Θ(Q 2 )$$ * **Sum of First Powers of 2**: $$1+2+4+8+...+Q=2Q−1=Θ(Q)$$ You saw both of these above, and they'll return again and again in runtime analysis. --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://cs61b-2.gitbook.io/cs61b-textbook-spring-2026/12.-asymptotics-ii/12.4-for-loops-print-party.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.