Search code examples
notationbig-o

Finding Theta Notation in terms of n

Find a Θ notation in terms of n for the number of times the statement x = x + 1 is executed in the segment below:

i = 1
while (i < n^2)
    x = x + 1
    i = 3i

I know that i has a growth rate of O(3^k), but I am not sure how to get Θ notation in terms of n.

Solution

  • You have to find out, given n, how many times can you perform i = 3*i, starting from i = 1 before i >= n^2. You already know that after k steps, i = 3^k, so your task is solving

    3^(k-1) < n^2 <= 3^k

    , that is, write k as a function of n.