Complexity / Runtime Analysis: Level 2 Challenges Practice Problems Online

Winston, the pigeon

Back in 2009, citizens of South Africa were frustrated with internet speed. They raced a carrier pigeon against their ISP. The pigeon had a 4 GB USB stick affixed to its leg and was taught to fly to an office, 50 miles away.

The pigeon won by a huge margin -- only 4% of the data was sent through the internet services as the pigeon reached the destination in 2 hours.

You may read the fascinating story, here

As a sidenote, notice that the pigeon would take the same time to carry a data packet of 10 KB to the same destination 50 miles away. But then again, it'd take the same time to carry a 1 TB hard drive, as well.

If $n$ is the number of bits being transmitted, how would you characterize the time taken to transmit data by the pigeon (for a reasonable amount of data)?

Inspired by Gayle Laakmann McDowell

def fun(n):
    if n==1:
        return 1
    else:
        return fun(n-1) + fun(n-1)

What is the time complexity of the above function?

True or false:

If a code has $O(1)$ time complexity, then the runtime of the code is exactly the same for all possible inputs (intended inputs).

Notation:

$O(\cdot)$ is the Big O Notation.

Concept Quizzes

Challenge Quizzes

Complexity / Runtime Analysis: Level 2 Challenges

Inspired by Gayle Laakmann McDowell